用户工具

站点工具


2020-2021:teams:wangzai_milk:20200718比赛记录

差别

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

到此差别页面的链接

两侧同时换到之前的修订记录 前一修订版
后一修订版
前一修订版
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:
  
 ===== 题解 ===== ===== 题解 =====
-==== Basic Gcd Problem ​====+==== 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]==0break;+            ​}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%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 1;i<1000000;i++) +    scanf("​%s",​s); 
-        for (int 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 strlen(s); 
-    ​scanf("​%d",&​cas); +    int st 0,x
-    ​while ​(cas--) { +    for (int 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;
 } }
2020-2021/teams/wangzai_milk/20200718比赛记录.1595424499.txt.gz · 最后更改: 2020/07/22 21:28 由 infinity37