这里会显示出您选择的修订版和当前版本之间的差别。
两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
2020-2021:teams:wangzai_milk:20200718比赛记录 [2020/07/22 21:28] infinity37 [B - Basic Gcd Problem] |
2020-2021:teams:wangzai_milk:20200718比赛记录 [2020/07/23 20:44] (当前版本) wzx27 |
||
---|---|---|---|
行 15: | 行 15: | ||
===== 题解 ===== | ===== 题解 ===== | ||
- | ==== B - Basic Gcd Problem ==== | + | ==== A - Clam and Fish ==== |
- | 题意:当$x>1$时,$f_c(x)=max_{i=1…x-1}c·f_c(gcd(i,x))$,当$x=1$时,$f_c(x)=1$,给出若干$n,c$,求$f_c(n)$ | + | 依次经过 $n$ 个格子,每个格子上可能有 $\text{fish}$ 或 $\text{clam}$。 |
- | 题解:n的质因数的数目为$cnt_n$,可以分析出来问题的答案是$c^{cnt_n}$,硬分解可能会T,写个递推求质因数数目就行。 | + | 每个格子上可以下面的选一个操作: |
- | <hidden><code cpp> | + | 如果有 $\text{clam}$,可以制作一个鱼饵 |
- | #include <bits/stdc++.h> | + | |
+ | 如果有 $\text{fish}$,可以得到一条鱼 | ||
+ | |||
+ | 消耗一个鱼饵获得一条鱼 | ||
+ | |||
+ | 什么事都不做 | ||
+ | |||
+ | 显然有鱼的位置选操作三。剩下的有能制作鱼饵就制作鱼饵,否则就用鱼饵捕鱼。最后加上剩下鱼饵的二分之一。 | ||
+ | |||
+ | <hidden code> <code cpp> | ||
+ | #include<bits/stdc++.h> | ||
+ | #define ALL(x) (x).begin(),(x).end() | ||
+ | #define ll long long | ||
+ | #define ull unsigned long long | ||
+ | #define pii_ pair<int,int> | ||
+ | #define mp_ make_pair | ||
+ | #define pb push_back | ||
+ | #define fi first | ||
+ | #define se second | ||
+ | #define rep(i,a,b) for(int i=(a);i<=(b);i++) | ||
+ | #define per(i,a,b) for(int i=(a);i>=(b);i--) | ||
+ | #define show1(a) cout<<#a<<" = "<<a<<endl | ||
+ | #define show2(a,b) cout<<#a<<" = "<<a<<"; "<<#b<<" = "<<b<<endl | ||
using namespace std; | using namespace std; | ||
- | #define maxn 1000005 | + | const ll INF = 1LL<<60; |
- | using namespace std; | + | const int inf = 1<<30; |
- | typedef long long ll; | + | const int maxn = 2e6+5; |
- | const int mod = 1e9+7; | + | inline void fastio() {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);} |
- | bool isprime[maxn]; | + | |
- | int prime[maxn]; | + | char s[maxn]; |
- | int f[maxn]; | + | int main() |
- | int cnt=0; | + | { |
- | void PJ(){ | + | fastio(); |
- | memset(isprime,0,sizeof(isprime)); | + | int _; char x; |
- | cnt=0; | + | for(cin>>_;_;_--){ |
- | for(int i=2;i<=1000000;i++){ | + | int n; cin>>n; |
- | if(!isprime[i]){ | + | cin>>s+1; |
- | prime[cnt++]=i; | + | int ans = 0,cnt = 0; |
- | } | + | rep(i,1,n){ |
- | for(int j=0;j<cnt&&prime[j]*i<=maxn;j++){ | + | if(s[i]=='0'){ |
- | isprime[prime[j]*i]=1; | + | if(cnt) ans++,cnt--; |
- | if(i%prime[j]==0) break; | + | }else if(s[i]=='1'){ |
+ | cnt++; | ||
+ | } | ||
+ | else ans++; | ||
} | } | ||
+ | ans += cnt/2; | ||
+ | cout<<ans<<endl; | ||
} | } | ||
+ | return 0; | ||
} | } | ||
- | ll quick_pow(ll x,int y) { | + | |
- | ll ans = 1; | + | </code> </hidden> |
- | while(y) { | + | \\ |
- | if (y&1) | + | |
- | ans = (ans*x)%mod; | + | ==== B - Classical String Problem ==== |
- | x = x*x%mod; | + | |
- | y >>= 1; | + | 题意:两种操作,把字符串最后x个接到前面,把字符串最前面x个接到后面。最后询问一次当前字符串。 |
- | } | + | |
- | return ans; | + | 题解:相当于把字符串搞成一个环,有一个指针指着开头,每次操作相当于动指针,就每次加减移动字符数然后模长度就好了。 |
- | } | + | |
+ | <hidden><code cpp> | ||
+ | #include <bits/stdc++.h> | ||
+ | using namespace std; | ||
+ | const int N = 2e6+5; | ||
+ | char s[N]; | ||
int main() | int main() | ||
{ | { | ||
- | PJ(); | + | int Q; |
- | for (int i = 1;i<= 1000000;i++) | + | scanf("%s",s); |
- | for (int j = 0;j<cnt&&(ll)i*prime[j]<=1000000ll;j++) | + | scanf("%d",&Q); |
- | f[i*prime[j]] = f[i]+1; | + | char op[3]; |
- | int cas; | + | int n = strlen(s); |
- | scanf("%d",&cas); | + | int st = 0,x; |
- | while (cas--) { | + | for (int i = 1;i<= Q;i++) { |
- | int n,c; | + | scanf("%s%d",op,&x); |
- | scanf("%d%d",&n,&c); | + | if (op[0] == 'A') { |
- | int y = f[n]; | + | x--; |
- | printf("%lld\n",quick_pow(c,y)); | + | int pos = ((st+x)%n+n)%n; |
+ | printf("%c\n",s[pos]); | ||
+ | } else { | ||
+ | st = ((st+x)%n+n)%n; | ||
+ | } | ||
} | } | ||
return 0; | return 0; | ||
行 123: | 行 160: | ||
} | } | ||
} | } | ||
+ | return 0; | ||
+ | } | ||
+ | </code></hidden> | ||
+ | \\ | ||
+ | ==== D - Points Construction Problem ==== | ||
+ | |||
+ | 题意:给一个坐标轴,在整数点上染色,一开始所有的都是白色,要求染n个,使得有m对相邻的点颜色不同。 | ||
+ | |||
+ | 题解:构造,首先可以发现只有m为偶数的时候有方案,然后对于一个新染色点,可能多4对,2对或0对,然后枚举多4对的有几个点,2对的有几个点,算出0对的有几个点,然后先一行空一格染一个,染4对的,然后再最后一个4对的上侧和右侧增加2对的,看剩下的0对的能不能被完全放进这个L形里。可以就可以,不行就没了。 | ||
+ | |||
+ | <hidden><code cpp> | ||
+ | #include <bits/stdc++.h> | ||
+ | using namespace std; | ||
+ | const int N = 55; | ||
+ | int ans[N][2]; | ||
+ | int n,m; | ||
+ | int main() | ||
+ | { | ||
+ | int cas; | ||
+ | scanf("%d",&cas); | ||
+ | while (cas--) { | ||
+ | int n,m; | ||
+ | scanf("%d%d",&n,&m); | ||
+ | int minans = 4*n; | ||
+ | for (int i = 1;i<= n;i++) { | ||
+ | int x=i;int y = n/x; | ||
+ | if (n > x*y) | ||
+ | minans=min(minans,2*(x+y+1)); | ||
+ | else minans = min(minans,2*(x+y)); | ||
+ | } | ||
+ | bool find = false; | ||
+ | for (int cnt4 = 1;cnt4<=n && !find;cnt4++) { | ||
+ | for (int cnt2 = 0;cnt2+cnt4<=n && !find;cnt2++) { | ||
+ | if (cnt2*2+cnt4*4!=m)continue; | ||
+ | int cnt0 = n-cnt4-cnt2; | ||
+ | int x = cnt2/2;int y = cnt2-x; | ||
+ | if (cnt0 <= x*y) { | ||
+ | find = true; | ||
+ | int tmp = 0; | ||
+ | for (int i = 1;i<= cnt4;i++) | ||
+ | ans[++tmp][0] = i<<1; | ||
+ | for (int i = 1;i<= x;i++) { | ||
+ | tmp++; | ||
+ | ans[tmp][0] = ans[cnt4][0]+i; | ||
+ | ans[tmp][1] = ans[cnt4][1]; | ||
+ | } | ||
+ | for (int i = 1;i<= y;i++) { | ||
+ | tmp++; | ||
+ | ans[tmp][0] = ans[cnt4][0]; | ||
+ | ans[tmp][1] = ans[cnt4][1]+i; | ||
+ | } | ||
+ | for (int i = 0;i< cnt0;i++) { | ||
+ | int tx = i%x+1,ty = i/x+1; | ||
+ | tmp++; | ||
+ | ans[tmp][0] = ans[cnt4][0]+tx; | ||
+ | ans[tmp][1] = ans[cnt4][1]+ty; | ||
+ | } | ||
+ | } | ||
+ | } | ||
+ | } | ||
+ | if (find) { | ||
+ | printf("Yes\n"); | ||
+ | for (int i = 1;i<= n;i++) | ||
+ | printf("%d %d\n",ans[i][0],ans[i][1]); | ||
+ | } else { | ||
+ | printf("No\n"); | ||
+ | } | ||
+ | } | ||
return 0; | return 0; | ||
} | } |