2021-01-29 16:03 已编辑北京交通大学 Java

关注

小白月赛题1

小白月赛31

https://ac.nowcoder.com/acm/contest/10746

A-A｜B：动态规划

https://ac.nowcoder.com/acm/contest/10746/A

题目大意：

给定a和x，找出有多少个b满足 1<= b <= x , a|b = a+b

思路：

我们先把a和x用二进制形式表示，然后从最高位到最低位填满b。

如果要a|b=a+b，那么a和b相同的位不能位1，只能为零。又因为1<=b<=x，如果a的第i位是0，x的第i位是0，并且x的前缀和b的前缀相同，那么b的第i位只能0，否则b>x,但如果x的第i位是1，那么

b的第i位可以取0或1.

所有我们要求从第i位开始x的前缀和和b的前缀相等和不等的填充方法数，用dp[i][0]来表示b的第i位的前缀和x的第i位前缀不相等的方法数，dp[i][1]相等的方法数。

转移方程：看注释

初值：dp[30][1] = 1

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <stack>
#include <queue>
#include <string.h>
#include <cmath>
#include <bitset> 
#include <set>
#include <map>
#include <list>
#define ull unsigned long long
#define ll long long
const int inf = 0x3f3f3f3f;
const int mod = 1e9+7;
const int N = 500005;
const ll ds = 1e15+7;
const double p1 = 3.141592653589793238462643383;
const ull res = 233;

using namespace std;

ll dp[55][2];
int main()
{
	int t,a,b,x;
	cin >> t;
	while(t--){
		cin >> a >> x;
		ll ans = 1;
		memset(dp,0,sizeof(dp));
		dp[30][1] = 1;
		for(int i = 29; i >= 0; i--){
			//a i 1
			if(a&(1<<i)){
				//b i 0 ,b的第i为必填0 
				if(x&(1<<i)) dp[i][0] = dp[i+1][0] + dp[i+1][1];//x的第i位与b的第i位不同 
				else{//相同 
				    //结果和之前的相同  
					dp[i][1] = dp[i+1][1];
            		dp[i][0] = dp[i+1][0];
				} 
			}
			else{
				//b i 0/1
				if(x&(1<<i)){
					//x i 1
					dp[i][0] = dp[i+1][0]*2 + dp[i+1][1];//b的第i位取0,不同了 
					dp[i][1] = dp[i+1][1];
					//或者dp[i][0] = dp[i+1][0];   //取1，相同，那结果和之前的相同 
					//dp[i][1] = dp[i+1][1];
				}
				else{
					//x i 0
					//只有前缀不等才能前1，否则只能填0，同样分两种情况讨论 
					dp[i][0] = dp[i+1][0]*2;
					dp[i][1] = dp[i+1][1];
				}
			} 
		}
		cout << dp[0][0] + dp[0][1] - 1 << endl;
	}
 	return 0;
}

C-图像存储：dfs判连通块+哈希

https://ac.nowcoder.com/acm/contest/10746/C

思路：

从某个点开始深度优先搜索下去得到dfs序，这些点是一块，并标记已经走过，再从下一个点进行判断。

然后用哈希值判断各个联通块是否可以平移重合在一起。

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <stack>
#include <queue>
#include <string.h>
#include <cmath>
#include <bitset> 
#include <set>
#include <map>
#include <list>
#define ull unsigned long long
#define ll long long
const int inf = 0x3f3f3f3f;
const int mod = 1e9+7;
const int N = 500005;
const ll ds = 1e15+7;
const double p1 = 3.141592653589793238462643383;
const ll res = 233;

using namespace std;

char s[1005][1005];
int dir[4][2] = {{0,1},{0,-1},{1,0},{-1,0}};
int vis[1005][1005],n,m;
ll k = 0;
map<ll,ll>mp;

bool check(int x,int y)
{
	if(x < 0 || x >= n || y < 0 || y >= m) return false;
	return true;
}

void dfs(int x,int y)
{
	for(int i = 0; i < 4; i++){
		int X = x+dir[i][0];
		int Y = y+dir[i][1];
		if(check(X,Y) && !vis[X][Y] && s[X][Y] == '1'){
			vis[X][Y] = 1;
			dfs(X,Y);
			k = (k*res%mod+5)%mod;
		} 
		k = (k*res%mod+13)%mod;
	}
}

int main()
{
	while(~scanf("%d%d",&n,&m)){
        if(n == 0 && m == 0) break;
		mp.clear();
		//getchar();
		memset(vis,0,sizeof(vis));
		for(int i = 0; i < n; i++){
			scanf("%s",s[i]);
		}
		int cnt = 0,ans = 0;
		for(int i = 0; i < n; i++){
			for(int j = 0; j < m; j++){
				if(s[i][j] == '1' && !vis[i][j]){
					cnt++;
					vis[i][j] = 1;
					k = 0;
					dfs(i,j);
					if(!mp[k]) ans++,mp[k] = 1;
				}
			}
		}
		printf("%d %d\n",cnt,ans);
	}
 	return 0;
}

E-解方程：数论

https://ac.nowcoder.com/acm/contest/10746/E

题目大意：

已知正整数a，b，求正整数x，y，满足a*x+b*y=x*y的组数。

思路：

式子做下变换

a*x+b*y+a*b=x*y+a*b

a*b = x*y-a*x-b*y+a*b

a*b = (x-b)*(y-a)

所以就是求a*b的因子有多少个。

因为 1<=a,b <= 1e6, 则1<=a*b<=1e12

那么不能直接求a*b的因子个数，可以将a*b作质因子分解，我们知道 $N=p_{1}^{c_{1}}p_{2}^{c_{2}}p_{3}^{c_{3}}...p_{n}^{c_{n}}$ ,N的因子个数就为 $(c_{1}+1)(c_{2}+1)...(c_{n}+1)$

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <stack>
#include <queue>
#include <string.h>
#include <cmath>
#include <bitset> 
#include <set>
#include <map>
#include <list>
#define ull unsigned long long
#define ll long long
const int inf = 0x3f3f3f3f;
const int mod = 1e9+7;
const int N = 500005;
const ll ds = 1e15+7;
const double p1 = 3.141592653589793238462643383;
const ull res = 233;

using namespace std;

ll solve(ll cj)
{
	ll ans = 1;
	int flag = 0;
	for(ll i = 2; i*i <= cj; i++){
		if(cj%i == 0){
			flag = 1;
			int cnt = 0;
			while(cj%i == 0) {
				cj /= i;
				cnt++;
			}
			ans = (cnt+1)*ans;
		}
	}
	if(cj > 1) ans *= 2;
	return ans;
}

int main()
{
	int a,b,t;
	cin >> t;
	while(t--){
		cin >> a >> b;
		ll cj = 1ll*a*b;
        if(cj == 1) cout << 1 << endl;
        else cout << solve(cj) << endl;
	}
 	return 0;
}

F-消去整数：数论

https://ac.nowcoder.com/acm/contest/10746/F

题目大意：

给一个正整数n，让n依次减去1，2，3...直至减位零为止，如果不能减了，则加上n再重复，问需要重复几个这样的过程。

思路：

如果能够一次完成，那么答案为1，

如果不行，那假设减到了x，n剩余y，可知y<x，那再加上n之后，n变成n+y，继续从1开始减，因为y < x，所以最后只能减到x，如果y+y > x,

那么n剩余y+y-x，同理第3次后n剩余y+y+y-x-x，同理重复i次后剩余y*i-k*x，如果y*i-k*x = 0,即是x的最小公倍数是y*i，答案就是i。

i*y = 0 (mod x)

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <stack>
#include <queue>
#include <string.h>
#include <cmath>
#include <bitset> 
#include <set>
#include <map>
#include <list>
#define ull unsigned long long
#define ll long long
const int inf = 0x3f3f3f3f;
const int mod = 1e9+7;
const int N = 500005;
const ll ds = 1e15+7;
const double p1 = 3.141592653589793238462643383;
const ull res = 233;

using namespace std;

int solve(int n)
{
	int x = 1;
	while(n >= x){
		n -= x;
		x++;
	}
	for(int i = 1; ;i++){
		if(i*n%x == 0) {
			return i;
		}
	}
}

int main()
{
	int t,n;
	cin >> t;
	while(t--){
		cin >> n;
		cout << solve(n) << endl;
	} 
 	return 0;
}

小白月赛17

https://ac.nowcoder.com/acm/contest/1085#question

F-小黄鸭：数学积分+二分答案

https://ac.nowcoder.com/acm/contest/1085/F

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <stack>
#include <queue>
#include <string.h>
#include <cmath>
#include <bitset> 
#include <set>
#include <map>
#include <list>
#define ull unsigned long long
#define ll long long
const int inf = 0x3f3f3f3f;
const int mod = 1e9+7;
const int N = 500005;
const ll ds = 1e15+7;
const double p1 = 3.141592653589793238462643383;
const ll res = 233;

using namespace std;

int main()
{
	int R,m;
	cin >> R >> m;
	double res = 0,l = 0,r = 2*R;
	while(r-l > 1e-4){
		double mid = (l+r)/2.0;
		if(p1*(-1*mid*mid*mid/3.0+mid*mid*R) > m)
			r = mid; 
		else
		    l = mid;
	}
//	printf("%.2f\n",res);
    double ans = 2*R-r;
	printf("%.2f",ans);
 	return 0;
}

G-区间求和：莫队(模板题)

https://ac.nowcoder.com/acm/contest/1085/G

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <stack>
#include <queue>
#include <string.h>
#include <cmath>
#include <bitset> 
#include <set>
#include <map>
#include <list>
#define ull unsigned long long
#define ll long long
const int inf = 0x3f3f3f3f;
const int mod = 1e9+7;
const int N = 500005;
const ll ds = 1e15+7;
const double p1 = 3.141592653589793238462643383;
const ll res = 233;

using namespace std;


int n,m,block,l = 1,r = 0;
ll now = 0;
struct Node{
	int l,r,xb;
//	bool operator < (const Node &a) const{
//	    if(a.l/block == l/block) return a.r > r;
//	    else return a.l/block > l/block;
//	}
}node[100005];

ll a[100005],cnt[100005];
ll ans[100005];
void add(int t)
{
	now -= cnt[a[t]]*a[t]*cnt[a[t]];
	cnt[a[t]]++;
	now += cnt[a[t]]*a[t]*cnt[a[t]];
}

void del(int t)
{
	now -= cnt[a[t]]*a[t]*cnt[a[t]];
//	if(cnt[a[t]] > 0){//这步不能加
		cnt[a[t]]--;
		now += cnt[a[t]]*a[t]*cnt[a[t]];
//	}
}

bool cmp(Node q1,Node q2)
{
	if(q1.l/block == q2.l/block) return q1.r < q2.r;
	return q1.l/block < q2.l/block;
}

int main()
{
	scanf("%d%d",&n,&m);
	block = sqrt(n);
	for(int i = 1; i <= n; i++) scanf("%lld",&a[i]);
	for(int i = 1; i <= m; i++){
		scanf("%d%d",&node[i].l,&node[i].r);
		node[i].xb = i;
	}
	sort(node+1,node+m+1,cmp);
	for(int i = 1; i <= m; i++){
		while(l < node[i].l) del(l++);
		while(l > node[i].l) add(--l);
		while(r < node[i].r) add(++r);
		while(r > node[i].r) del(r--);
		ans[node[i].xb] = now;
	}
	for(int i = 1; i <= m; i++){
		printf("%lld\n",ans[i]);
	}
 	return 0;
}

H-取数游戏：期望dp

https://ac.nowcoder.com/acm/contest/1085/H

思路：

求期望，概率等一般考虑用dp。

找状态：dp[i][j]：表示拿i次后桌子上有j个球的概率。

状态转移：dp[i][j] = dp[i-1][j-1]*(c-j+1)/c+dp[i-1][j+1]*(j-1)/c 第i次从剩余（c-j+1）种球拿一个桌子上成为j个，从j+1种球拿一个和桌子上的某个球相同，拿走一个，桌子上剩余j个。

初值：dp[0][0] = 1.00

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <stack>
#include <queue>
#include <string.h>
#include <cmath>
#include <bitset> 
#include <set>
#include <map>
#include <list>
#define ull unsigned long long
#define ll long long
const int inf = 0x3f3f3f3f;
const int mod = 1e9+7;
const int N = 500005;
const ll ds = 1e15+7;
const double p1 = 3.141592653589793238462643383;
const ll res = 233;

using namespace std;

double dp[10050][105];
int main()
{
	int c,m;
    ll n;
	scanf("%d%lld%d",&c,&n,&m);
	if((n&1) != (m&1)){
		printf("0.000\n");
		return 0;
	}
	if(n >= 1e4) n = 1e4+(n%2);
	dp[0][0] = 1.00;
	for(int i = 1; i <= n; i++){
		for(int j = 0; j <= c; j++){
			if(j) dp[i][j] = dp[i-1][j-1]*1.0*((c-j+1)*1.0/c*1.0) + 1.0*dp[i-1][j+1]*((j+1)*1.0/c*1.0);
		    else dp[i][j] = dp[i-1][j+1]*1.0*((j+1)*1.0/c*1.0);
		}
	}
	printf("%.3lf",dp[n][m]);
 	return 0;
}

小白月赛16

https://ac.nowcoder.com/acm/contest/949#question

D-小阳买水果：前缀和

https://ac.nowcoder.com/acm/contest/949/D

大意：

给定n个水果的满意度，只能买一段连续的水果，在保证满意度大于零的情况下长度最大是多少。

思路;

重载结构体，按前缀和从小到大排序，这样相减后中间那段一定大于零，前缀和相同按下标从大到小排序，可以保证排除某段连续为零的情况。为了求到最大值，维护一个最小的下标min_xb。

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <stack>
#include <queue>
#include <string.h>
#include <cmath>
#include <bitset> 
#include <set>
#include <map>
#include <list>
#define ull unsigned long long
#define ll long long
const int inf = 0x3f3f3f3f;
const int mod = 911451407;
const int N = 500005;
const ll ds = 1e15+7;
const double p1 = 3.141592653589793238462643383;
const ll res = 233;

using namespace std;

struct Node{
	int xb;
	ll x;
	bool operator < (const Node &a) const{
	    if(a.x == x) return a.xb < xb;
	    else return a.x > x;
	}
}node[2000005];

int main()
{
	int x,n;
	scanf("%d",&n);
	for(int i = 1; i <= n; i++){
		scanf("%d",&x);
		node[i].xb = i;
		node[i].x = node[i-1].x+x;
	}
	sort(node,node+n+1);
	int ans = 0,min_xb = node[0].xb;
	for(int i = 0; i <= n; i++){
		ans = max(ans,node[i].xb-min_xb);
		min_xb = min(min_xb,node[i].xb);
	}
	printf("%d",ans);
 	return 0;
}

小白月赛文章被收录于专栏

希望通过写小白月赛来提升自己的算法能力。