差别

这里会显示出您选择的修订版和当前版本之间的差别。

--- 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;
-#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()
 {
-    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;
@@ 行 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;
 }

CVBB ACM Team

用户工具

站点工具

差别

页面工具