小白月赛题1
小白月赛31
A-A｜B：动态规划
题目大意：
给定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判连通块+哈希
思路：
从某个点开始深度优先搜索下去得到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-解方程：数论
题目大意：
已知正整数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的因子个数就为(c_%7B2%7D%2B1)...(c_%7Bn%7D%2B1))
#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-消去整数：数论
题目大意：
给一个正整数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
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-区间求和：莫队(模板题)
#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
思路：
求期望，概率等一般考虑用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
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;
} 小白月赛 文章被收录于专栏
希望通过写小白月赛来提升自己的算法能力。
投递4399游戏等公司10个岗位 >
