[关闭]
@baobaobear 2020-05-19T05:55:42.000000Z 字数 7219 阅读 196

Contest 28

contest

A chinanb

  1. #include<stdio.h>
  2. #include<algorithm>
  3. #include<math.h>
  4. #include<string.h>
  5. typedef long long ll;
  6. using namespace std;
  7. int main()
  8. {
  9.     double a,b;
  10.     int n;
  11.     scanf("%d",&n);
  12.     scanf("%lf %lf",&a,&b);
  13.     n-=1;
  14.     while(n--)
  15.     {
  16.         double c,d;
  17.         scanf("%lf %lf",&c,&d);
  18.         if((d/c)-(b/a)>0.05)   printf("better\n");
  19.         else if((b/a)-(d/c)>0.05)   printf("worse\n");
  20.         else  printf("same\n");
  21.     }
  22.     return 0;
  23. }

B 2018112559

  2. #include<iostream>
  3. #include<cmath>
  4. #include<iomanip>
  5. #include<stack>
  6. #include<vector>
  7. #include<string>
  8. #include<algorithm>
  9. #include<queue>
  10. #include<map>
  11. using namespace std;
  13. int main() {
  14.     priority_queue<int> p, q;
  15.     int n, inc, dec, x, y;
  16.     long long int c = 0;
  17.     cin >> n >> inc >> dec;
  18.     while (n--) {
  19.         cin >> x >> y;
  20.         p.push(x);
  21.         q.push(y);
  22.     }
  23.     for (int i = p.size(); i > 0; i--) {
  24.         x = p.top();
  25.         y = q.top();
  26.         p.pop();
  27.         q.pop();
  28.         c += (x > y ? (dec * (x - y)) : (inc * (y - x)));
  29.     }
  30.     cout << c;
  31. }

C 541907190117

  1. #include<set>
  2. #include<map>
  3. #include<list>
  4. #include<cmath>
  5. #include<stack>
  6. #include<queue>
  7. #include<cstdio>
  8. #include<cctype>
  9. #include<string>
  10. #include<vector>
  11. #include<climits>
  12. #include<cstring>
  13. #include<cstdlib>
  14. #include<iostream>
  15. #include<sstream>
  16. #include<algorithm>
  17. #define endl '\n'
  18. #define rtl rt<<1
  19. #define rtr rt<<1|1
  20. #define lson rt<<1, l, mid
  21. #define rson rt<<1|1, mid+1, r
  22. #define maxx(a, b) (a > b ? a : b)
  23. #define minn(a, b) (a < b ? a : b)
  24. #define zero(a) memset(a, 0, sizeof(a))
  25. #define INF(a) memset(a, 0x3f, sizeof(a))
  26. #define IOS ios::sync_with_stdio(false)
  27. #define _test printf("============\n")
  28. using namespace std;
  29. typedef long long ll;
  30. typedef pair<int, int> P;
  31. typedef pair<ll, ll> P2;
  32. const double pi = acos(-1.0);
  33. const double eps = 1e-7;
  34. const ll MOD =  1000000007LL;
  35. const int INF = 0x3f3f3f3f;
  36. const int NIL = -1;
  37. template<typename T> void read(T &x){
  38.     x = 0;char ch = getchar();ll f = 1;
  39.     while(!isdigit(ch)){if(ch == '-')f*=-1;ch=getchar();}
  40.     while(isdigit(ch)){x = x*10+ch-48;ch=getchar();}x*=f;
  41. }
  42. const int maxn = 5e5+10;
  43. char str[maxn];
  44. vector<int> num[26];
  45. int main() {
  46.     scanf("%s", str);
  47.     int len = strlen(str);
  48.     for (int i = len-1; i>=0; --i)
  49.         num[str[i]-'a'].push_back(i);
  50.     bool flag = false;
  51.     for (int i = 0; i<len; ++i) 
  52.         for (int j = 0; j<=str[i]-'a'; ++j) {
  53.             if (num[j].empty()) continue;
  54.             int tmp = num[j][0];
  55.             if (tmp>i&&j<str[i]-'a') {
  56.                 swap(str[tmp], str[i]);
  57.                 printf("%s\n", str);
  58.                 return 0;
  59.             }
  60.             else if (tmp>i&&j==str[i]-'a') flag = true; 
  61.         }
  62.     if (flag) printf("%s\n", str);
  63.     else {
  64.         swap(str[len-2], str[len-1]);
  65.         printf("%s\n", str);
  66.     }
  67.     return 0;
  68. }

D Kevin7Zz

  1. #pragma GCC optimize(2)
  2. #include <cstdio>
  3. #include <iostream>
  4. #include <algorithm>
  5. #include <cstring>
  6. #include <queue> //priority_queue<int, vector<int>, greater<int> > q;从小到大
  7. #include <map>
  8. #include <set> //multiset set<int,greater<int>>大到小
  9. #include <vector>// vector<int>().swap(v);清空释放内存
  10. #include <stack>
  11. #include <cmath> // auto &Name : STLName  Name.
  12. #include <utility>
  13. #include <sstream>
  14. #include <string>//__builtin_popcount(ans);//获取某个数二进制位1的个数
  15. #define mod 1000000007
  16. #define mod9 998244353
  17. typedef unsigned long long ull;
  18. typedef long long ll;
  19. typedef double db;
  20. typedef long double ld;
  21. const db eps=1e-7;
  22. #define PII pair<int,int>
  23. //const db pi=acos(-1);
  24. const int INF = 0x3f3f3f3f;
  25. const ll inf=0x3f3f3f3f3f3f3f3f;
  26. #define rep(i,be,en) for (int i=be;i<=en;i++)
  27. #define per(i,be,en) for (int i=en;i>=be;i--)
  28. using namespace std;
  29. const int N=1e6+3;
  31. int T,n,m,k,ans=0;
  32. char a[N]={0};
  33. int b[N]={0};
  34. int main(){
  35.     scanf("%s",a+1);
  36.     n=strlen(a+1);
  37.     for(int i=1;i<=n;i++){
  38.         if(a[i]>='A'&&a[i]<='Z') ans++;
  39.         b[i]=ans;
  40.     }
  41.     int maxn=INF;
  42.     for(int i=0;i<=n;i++){
  43.         maxn=min(maxn,ans-b[i]+i-b[i]);
  44.     }
  45.     printf("%d\n",maxn);
  46.     return 0;
  47. }

E tiandaochouqin

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4. const int maxn=1e5+5;
  5. const int inf=0x3f3f3f3f;
  6. int n,dp[maxn],ans=0,a[maxn];
  7. int main()
  8. {
  9.         scanf("%d",&n);
  10.         for(int i=1;i<=n;++i) scanf("%d",&a[i]);
  11.         for(int i=1;i<=n;++i)
  12.         {
  13.             dp[a[i]]=dp[a[i]-1]+1;
  14.             ans=max(ans,dp[a[i]]);
  15.         }
  16.         printf("%d\n",n-ans);
  17. }

F tiandaochouqin

  1. #include<iostream>
  2. #include<algorithm> 
  3. #include<vector>
  4. #include<cstring>
  5. #include<queue>
  6. #include<cstdio>
  7. using namespace std;
  8. typedef long long ll;
  9. const int maxn=2e5+5;
  10. int top=0,prime[maxn],isprime[maxn],v[maxn],vis[maxn];
  11. void Prime(int n)
  12. {
  13.     for(int i=2;i<=n;++i)
  14.     {
  15.         if(!isprime[i]) prime[top++]=i;
  16.         for(int j=0;j<top;++j)
  17.         {
  18.             if(i*prime[j]>n) break;
  19.             isprime[i*prime[j]]=1;
  20.             if(i%prime[j]==0) break;
  21.         }
  22.     }
  23. }
  24. int bfs(int a,int b)
  25. {
  26.     queue<pair<int,int> >q;
  27.     q.push({a,0});
  28.     v[a]=1;
  29.     while(!q.empty())
  30.     {
  31.         int t=q.front().first,num=q.front().second;
  32.         q.pop();
  33.         if(t==b) return num;
  34.         int t1=t/1000,t2=t/100%10,t3=t/10%10,t4=t%10;
  35.         for(int i=1;i<=9;++i)
  36.         {
  37.             if(i==t1) continue;
  38.             int x=i*1000+t2*100+t3*10+t4;
  39.             if(vis[x]&&!v[x]) q.push({x,num+1}),v[x]=1;
  40.         }
  41.         for(int i=0;i<=9;++i)
  42.         {
  43.             if(i==t2) continue;
  44.             int x=t1*1000+i*100+t3*10+t4;
  45.             if(vis[x]&&!v[x]) q.push({x,num+1}),v[x]=1;
  46.         }
  47.         for(int i=0;i<=9;++i)
  48.         {
  49.             if(i==t3) continue;
  50.             int x=t1*1000+t2*100+i*10+t4;
  51.             if(vis[x]&&!v[x]) q.push({x,num+1}),v[x]=1;
  52.         }
  53.         for(int i=0;i<=9;++i)
  54.         {
  55.             if(i==t4) continue;
  56.             int x=t1*1000+t2*100+t3*10+i;
  57.             if(vis[x]&&!v[x]) q.push({x,num+1}),v[x]=1;
  58.         }
  59.     }
  60.     return -1;
  61. }
  62. int main()
  63. {
  64.     int T,a,b;
  65.     Prime(1e4);
  66.     for(int i=0;i<top&&prime[i]<1e4;++i)
  67.     if(prime[i]>=1000&&prime[i]<10000) vis[prime[i]]=1; 
  68.     scanf("%d",&T);
  69.     while(T--)
  70.     {
  71.         memset(v,0,sizeof(v));
  72.         scanf("%d %d",&a,&b);
  73.         if(!vis[b]){
  74.             puts("Impossible");continue;
  75.         }
  76.         int ans=bfs(a,b);
  77.         if(ans==-1) puts("Impossible");
  78.         else printf("%d\n",ans);
  79.     }
  80. }

G tiandaochouqin

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4. const int maxn=1e6+5; 
  5. const int mod=1e9+7;
  6. char s[maxn];
  7. ll dp[maxn][5],ans=0;
  8. int main()
  9. {
  10.     scanf("%s",s+1);
  11.     int len=strlen(s+1);
  12.     dp[0][1]=dp[0][3]=1;
  13.     for(int i=1;i<=len;++i)
  14.     {
  15.         if(s[i]=='0') dp[i][1]=(dp[i-1][2]+dp[i-1][1])%mod;
  16.         if(s[i]=='1') dp[i][2]=dp[i-1][0]%mod,dp[i][3]=(dp[i-1][1]+dp[i-1][2])%mod;
  17.         if(s[i]=='2') dp[i][4]=dp[i-1][0]%mod;
  18.         if(s[i]=='*') dp[i][0]=((dp[i-1][0]+dp[i-1][3])%mod+dp[i-1][4])%mod;
  19.         if(s[i]=='?') {
  20.             dp[i][1]=(dp[i-1][2]+dp[i-1][1])%mod;
  21.             dp[i][2]=dp[i-1][0]%mod,dp[i][3]=(dp[i-1][1]+dp[i-1][2])%mod;
  22.             dp[i][4]=dp[i-1][0]%mod;
  23.             dp[i][0]=((dp[i-1][0]+dp[i-1][3])%mod+dp[i-1][4])%mod;
  24.         }
  25.     }
  26.     printf("%lld\n",((dp[len][0]+dp[len][1])%mod+dp[len][2])%mod);
  27. }

H tiandaochouqin

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4. const int maxn=2e3+5;
  5. int tree[maxn*32][2],tot,ans=0,a[maxn],num[maxn*32];
  6. void insert(int x)
  7. {
  8.     int u=0;
  9.     for(int i=31;i>=0;--i)
  10.     {
  11.         int t=(((1LL<<i)&x)?1:0);
  12.         if(!tree[u][t]) tree[u][t]=++tot;
  13.         u=tree[u][t];
  14.         num[u]++;
  15.     }
  16. }
  17. void delet(int x)
  18. {
  19.     int u=0;
  20.     for(int i=31;i>=0;--i)
  21.     {
  22.         int t=(((1LL<<i)&x)?1:0);
  23.         u=tree[u][t];
  24.         num[u]--;
  25.     }
  26. }
  27. int query(int x)
  28. {
  29.     int u=0,res=0;
  30.     for(int i=31;i>=0;--i)
  31.     {
  32.         int t=(((1LL<<i)&x)?1:0);
  33.         if(tree[u][t^1]&&num[tree[u][t^1]]) u=tree[u][t^1],res+=(1LL<<i);
  34.         else u=tree[u][t];
  35.     }
  36.     return res;
  37. }
  38. int main()
  39. {
  40.     int T,n;
  41.     scanf("%d",&T);
  42.     while(T--)
  43.     {
  44.         ans=tot=0;
  45.         memset(tree,0,sizeof(tree));
  46.         memset(num,0,sizeof(num));
  47.         scanf("%d",&n);
  48.         for(int i=1;i<=n;++i) scanf("%d",&a[i]),insert(a[i]);
  49.         for(int i=1;i<=n;++i)
  50.         {
  51.             delet(a[i]);
  52.             for(int j=i+1;j<=n;++j)
  53.             {
  54.                 delet(a[j]);
  55.                 ans=max(ans,query(a[i]+a[j]));
  56.                 insert(a[j]);
  57.             }
  58.             insert(a[i]);
  59.         }
  60.         printf("%d\n",ans);
  61.     }
  62. }

I tiandaochouqin

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. const int INF = 0x3f3f3f3f;
  4. const int maxn=1e5+5;
  5. typedef long long ll;
  6. const ll mod = 9937;
  7. int pri[maxn],top = 0;
  8. bool vis[maxn];
  9. void prime()
  10. {
  11.     memset(vis, 0,sizeof(vis));
  12.     for(int i = 2; i < maxn; i++)
  13.     {
  14.         if(!vis[i]) pri[top++] = i;
  15.         for(int j = 0; j < top && i * pri[j] < maxn; j++)
  16.         {
  17.             vis[i *pri[j]] = 1;
  18.             if(i % pri[j] == 0)
  19.                 break;
  20.         }
  21.     }
  22. }
  24. ll get_phi(int x)
  25. {
  26.     ll res = x;
  27.     int ma = sqrt(x + 0.5);
  28.     for(int i = 0; i < top && pri[i] <= ma; i++)
  29.     {
  30.         if(x % pri[i] == 0)
  31.         {
  32.             while(x % pri[i] == 0)
  33.                 x /= pri[i];
  34.             res = res / pri[i] * (pri[i] - 1);
  35.         }
  36.     }
  37.     if(x > 1) res = res / x * (x - 1);
  38.     return res % mod;
  39. }
  40. ll quick(ll a, ll n)
  41. {
  42.     ll res = 1;
  43.     while(n)
  44.     {
  45.         if(n & 1)
  46.             res = res * a % mod;
  47.         a = a * a % mod;
  48.         n >>= 1;
  49.     }
  50.     return res;
  51. }
  52. int main()
  53. {
  54.     ll n, m;
  55.     prime();
  56.     while(scanf("%lld%lld", &n, &m)!=EOF)
  57.     {
  58.         ll ans = 0;
  59.         int ma = sqrt(n + 0.5);
  60.         for(int i = 1; i <= ma; i++)
  61.         {
  62.             if(n % i != 0)
  63.                 continue;
  64.             ans = (ans + get_phi(n / i) * quick(m, i) % mod + mod) % mod;
  65.             if(i != n / i)
  66.                 ans = (ans + get_phi(i) * quick(m, n / i) % mod + mod) % mod;
  67.         }
  68.         for(ll i = 0; i < mod; i++)
  69.             if(i * n % mod == ans % mod)
  70.             {
  71.                 ans = i;
  72.                 break;
  73.             }
  74.         printf("%lld\n", ans);
  75.     }   
  76.     return 0;
  77. }
添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注