[关闭]
@baobaobear 2020-05-03T10:38:43.000000Z 字数 12782 阅读 199

Contest 26

contest

A 1292224662

  1. #include<iostream>
  2. #include<cstdio>
  3. using namespace std;
  4. #define rep(i,a,n) for(int i=a;i<=n;i++)
  5. #define per(i,a,n) for(int i=n;i>=a;i--)
  6. #define pb push_back
  7. #define SZ(x) ((int)(x).size())
  8. typedef long long ll;
  9. typedef pair<int,int> pii;
  10. typedef double db;
  11. int n,ans; 
  12. int main(){
  13.     while(cin>>n){
  14.         ans=0;
  15.         while(n){
  16.             ans+=(n&1);
  17.             n/=2;
  18.         }
  19.         printf("%d\n",ans);
  20.     }
  21.     return 0;
  22. }

B 1292224662

  1. #include<iostream>
  2. #include<cstdio>
  3. #include<algorithm>
  4. using namespace std;
  5. #define rep(i,a,n) for(int i=a;i<=n;i++)
  6. #define per(i,a,n) for(int i=n;i>=a;i--)
  7. #define pb push_back
  8. #define SZ(x) ((int)(x).size())
  9. typedef long long ll;
  10. typedef pair<int,int> pii;
  11. typedef double db;
  12. int t,n;
  13. ll xx[10010],yy[10010],ans;
  14. int main(){
  15.     cin>>t;
  16.     while(t--){
  17.         cin>>n;
  18.         rep(i,1,n){
  19.             scanf("%lld",xx+i);
  20.         }
  21.         rep(i,1,n){
  22.             scanf("%lld",yy+i);
  23.         }
  24.         sort(xx+1,xx+1+n);
  25.         sort(yy+1,yy+1+n);
  26.         ans=0;
  27.         rep(i,1,n){
  28.             ans+=(xx[i]*yy[i]);
  29.         }
  30.         printf("%lld\n",ans);
  31.     }
  32.     return 0;
  33. }

C letianpai

  1. #include<stdio.h>
  2. #define LL long long
  4. int a[2000010] = { 0 };
  6. int main(void) {
  7.     int n;
  9.     scanf("%d", &n);
  10.     for (int i = 1; i <= n; i++)
  11.         a[i] = i;
  13.     int coun1 = 0, coun2 = 0, flag = 0;
  14.     for (int i = 1; i <= n + coun2; i++) {
  15.         coun1++;
  16.         if (coun1 == 1 && flag == 0) {
  17.             flag = 1;
  18.             printf("%d", a[i]);
  19.         }
  20.         else if (coun1 == 1 && flag)
  21.             printf(" %d", a[i]);
  23.         if (coun1 == 2) {
  24.             coun2++;
  25.             a[n + coun2] = a[i];
  26.             coun1 = 0;
  27.         }
  28.     }
  30.     return 0;
  31. }

D 1292224662

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define rep(i,a,n) for(int i=a;i<=n;i++)
  4. #define per(i,a,n) for(int i=n;i>=a;i--)
  5. #define pb push_back
  6. #define SZ(x) ((int)(x).size())
  7. typedef long long ll;
  8. typedef pair<int,int> pii;
  9. typedef double db;
  10. int n,tmp,s[50010];
  11. int mx[600010];
  12. int main(){
  13.     cin>>n;
  14.     rep(i,1,n){
  15.         cin>>tmp;
  16.         s[i]=s[i-1]+tmp;
  17.     }
  18.     memset(mx,-1,sizeof(mx));
  19.     rep(i,0,n){
  20.         s[i]=2*s[i]-i+50010;
  21.         mx[s[i]]=max(mx[s[i]],i);
  22.     }
  23.     int ans=0;
  24.     rep(i,1,n){
  25.         if(mx[s[i-1]]!=-1){
  26.             ans=max(ans,mx[s[i-1]]-i+1);
  27.         }
  28.     }
  29.     printf("%d\n",ans);
  30.     return 0;
  31. }

E baobaobear

  1. #define _CRT_SECURE_NO_WARNINGS
  2. #include <iostream>
  3. #include <algorithm>
  4. #include <string>
  5. #include <vector>
  6. #include <stack>
  7. #include <deque>
  8. #include <queue>
  9. #include <list>
  10. #include <limits>
  11. #include <set>
  12. #include <map>
  13. #include <functional>
  15. #include <stdint.h>
  16. #include <limits.h>
  17. #include <stdio.h>
  18. #include <stdlib.h>
  19. #include <string.h>
  20. #include <math.h>
  21. #include <time.h>
  23. using namespace std;
  24. typedef long long ll;
  26. #define io _g_io
  27. #define nl _g_pt_nl
  28. #define repi(i,b,e) for (int i = (b), _ = (e); i < _; ++i)
  29. #define rep(i,b,e)  for (int i = (b), _ = (e); i <= _; ++i)
  30. #define repr(i,b,e) for (int i = (b), _ = (e); i >= _; --i)
  32. static int sc_ret = 0;
  33. struct pt_nl {} _g_pt_nl;
  34. struct _sp
  35. {
  36.     _sp& operator >> (char& v) { sc_ret = scanf(" %c", &v); return *this; }
  37.     _sp& operator >> (int& v) { sc_ret = scanf("%d", &v); return *this; }
  38.     _sp& operator >> (unsigned& v) { sc_ret = scanf("%u", &v); return *this; }
  39.     _sp& operator >> (double& v) { sc_ret = scanf("%lf", &v); return *this; }
  40.     _sp& operator >> (char* v) { sc_ret = scanf("%s", v); return *this; }
  41.     _sp& operator >> (string& v) { sc_ret = (bool)(cin >> v); return *this; }
  42.     _sp& operator >> (ll& v) { sc_ret = read(v); return *this; }
  43.     _sp& ch(char& v) { v = sc_ret = getchar(); return *this; }
  44.     _sp& gets(char* v) { sc_ret = fgets(v, INT_MAX, stdin) != 0; v[strlen(v) - 1] = 0; return *this; }
  45.     operator bool() const { return sc_ret > 0; }
  46.     template <typename T>
  47.     int read(T& v)
  48.     {
  49.         T k = 1; v = 0;
  50.         int c = getchar();
  51.         while (c < '0' || c > '9')
  52.         {
  53.             if (c == '-') k = 0;
  54.             c = getchar();
  55.         }
  56.         while (c >= '0' && c <= '9') v = (v << 3) + (v << 1) + (c - 48), c = getchar();
  57.         if (k == 0) v = -v;
  58.         return c;
  59.     }
  60.     _sp& ln() { putchar('\n'); return *this; }
  61.     _sp& operator<<(const pt_nl& nl) { putchar('\n'); return *this; }
  62.     _sp& operator<<(char v) { putchar(v); return *this; }
  63.     _sp& operator<<(int v) { printf("%d", v); return *this; }
  64.     _sp& operator<<(unsigned v) { printf("%u", v); return *this; }
  65.     _sp& operator<<(double v) { printf("%.2f", v); return *this; }
  66.     _sp& operator()(const char* fmt, double v) { printf(fmt, v); return *this; }
  67.     _sp& operator<<(const char* v) { printf("%s", v); return *this; }
  68.     _sp& operator<<(string v) { printf("%s", v.c_str()); return *this; }
  69.     _sp& operator<<(ll v) { write(v); return *this; }
  70.     void flush() { fflush(stdout); }
  71.     template <typename T>
  72.     void write(T v)
  73.     {
  74.         int cnt = 0; char c[23];
  75.         if (v == 0) { putchar('0'); return; }
  76.         if (v < 0) putchar('-'), v = -v;
  77.         while (v) c[++cnt] = (v % 10) + 48, v /= 10;
  78.         while (cnt > 0) putchar(c[cnt--]);
  79.     }
  80.     template <typename T>
  81.     void ln(T* arr, int size, char split = ' ')
  82.     {
  83.         if (size > 0)
  84.         {
  85.             (*this) << arr[0];
  86.             for (int i = 1; i < size; ++i)
  87.                 putchar(split), (*this) << arr[i];
  88.         }
  89.         putchar('\n');
  90.     }
  91. }_g_io;
  93. const int inf = 0x3f3f3f3f;
  94. const int mod1e9 = 1000000007;
  95. const int mod998 = 998244353;
  96. const int mod = mod1e9;
  97. const int maxn = 2000000 + 10;
  100. void solve()
  101. {
  102.     int n, j = 0, lastsum = 0, lsum = 0;
  103.     int a[200];
  104.     ll sum = 0;
  105.     io >> n;
  106.     rep(i, 1, n) io >> a[i];
  107.     sort(a + 1, a + n + 1);
  108.     rep(i, 1, n)
  109.     {
  110.         lsum += i - 1;
  111.         lastsum += a[i];
  112.         if (lastsum == lsum)
  113.         {
  114.             sum += (n - j) * (i - j);
  115.             j = i;
  116.         }
  117.     }
  118.     io << sum << nl;
  119. }
  121. int main(void)
  122. {
  123.     int t;
  124.     solve();
  125.     return 0;
  126. }

F tiandaochouqin

  1. #include <iostream>
  2. #include <string.h>
  3. using namespace std;
  4. typedef long long ll;
  5. int n,m;
  6. ll dp[15][1<<11],temp;
  7. void dfs(int i,int p,int k)
  8. {
  9.     if(k>=m)
  10.     {
  11.         dp[i][p]+=temp;
  12.         return;
  13.     }
  14.     dfs(i,p,k+1);
  15.     if(k<=m-2 && !(p&1<<k) && !(p&1<<k+1))
  16.         dfs(i,p|1<<k|1<<k+1,k+2);
  17. }
  18. int main()
  19. {
  20.     while(scanf("%d%d",&n,&m)!=EOF)
  21.     {
  22.         if(n==0&&m==0) break;
  23.         memset(dp,0,sizeof(dp));
  24.         temp = 1;
  25.         dfs(1,0,0);
  26.         for(int i = 2; i<=n; i++)
  27.         {
  28.             for(int j = 0; j<1<<m; j++)
  29.             {
  30.                 if(dp[i-1][j]) temp = dp[i-1][j];
  31.                 else
  32.                     continue;
  33.                 dfs(i,~j&((1<<m)-1),0);
  34.             }
  35.         }
  36.         printf("%lld\n",dp[n][(1<<m)-1]);
  37.     }
  38.     return 0;
  39. }

G Howard_Turing

  1. #pragma GCC optimize("Ofast","inline")
  3. #include <cstdio>
  4. #include <cstdlib> 
  5. #include <algorithm>
  7. using namespace std;
  9. #define OUTS() printf("%lld\n", COUNT)
  10. #define work() for(long long i = 0; i <= 8; i++) (COUNT += f[NOW][i][0]) %= MOD
  11. #define INS() scanf("%lld", &n),scanf("%d", &k)
  12. #define MAIN() (f[NOW][j + h][(g + (i - 1)*h) % k] += f[NOW^1][j][g] * DO(arr[i - 1] + h - 1, h) % MOD) %= MOD
  14. const long long MOD = 1e9 + 7;
  16. bool AKIOI =true;
  18. long long f[2][9][710];
  19. long long COUNT = 0;
  20. long long arr[710], arr2[10];
  21. long long k, CNT, p[1500];
  22. long long arr3[710];
  24. long long read(){
  25.     long long ans=0,sign=1;
  26.     char ch=getchar();
  27.     while(isdigit(ch)){
  28.         ans=(ans<<1)+(ans<<3)+(ch^48),ch=getchar();
  29.     }
  30.         return ans*sign;
  31. }
  33. long long qpow(long long a, long long k) {
  34.     long long COUNT = 1;
  35.     while(k) {
  36.         if(k & 1) (COUNT *= a) %= MOD;
  37.         (a *= a) %= MOD; k /= 2;
  38.     } return COUNT;
  39. }
  41. long long DO(long long n, long long m) {
  42.     long long COUNT = 1;
  43.     for(long long i = n; i >= n - m + 1; i--) (COUNT *= i) %= MOD;
  44.     (COUNT *= arr2[m]) %= MOD;
  45.     return COUNT;
  46. }
  48. signed main(void) {
  49.     long long n; 
  50.     INS();
  51.     long long num = 0; long long pos = -1;
  52.     for(long long i = 1; i <= n; i++) {
  53.         num = (num * 10 + 1) % k;
  54.         if(arr3[num]) {pos = i; break;}
  55.         arr3[num] = i;
  56.         p[++CNT] = num;
  57.     } long long Q;
  58.     arr2[0] = 1; for(long long i = 1; i <= 8; i++) arr2[i] = arr2[i - 1] * i % MOD;
  59.     for(long long i = 1; i <= 8; i++) arr2[i] = qpow(arr2[i], MOD - 2);
  60.     if(pos == -1) {
  61.         for(long long i = 1; i <= CNT; i++) arr[p[i]]++;
  62.         Q = p[CNT];
  63.     } 
  64.         else {
  65.             for(long long i = 1; i < arr3[num]; i++) arr[p[i]]++;
  66.         n -= arr3[num] - 1;
  67.         long long dd = CNT - arr3[num] + 1;
  68.         for(long long i = arr3[num]; i <= CNT; i++) (arr[p[i]] += (long long)n / dd) %= MOD;
  69.         n %= dd;
  70.         for(long long i = 0; i < n; i++) (arr[p[i + arr3[num]]] += 1) %= MOD;
  71.         if(n == 0) n = dd;
  72.         Q = p[n + arr3[num] - 1];
  73.     }
  74.     long long NOW = 0; f[0][0][Q] = 1;
  75.     for(long long i = 1; i <= k; i++) {
  76.         NOW ^= 1;
  77.         for(long long j = 0; j <= 8; j++) for(long long u = 0; u < k; u++) f[NOW][j][u] = f[NOW ^ 1][j][u];
  78.         for(long long j = 0; j < 8; j++) {
  79.             for(long long g = 0; g < k; g++) if(f[NOW ^ 1][j][g]){
  80.                 for(long long h = 1; h <= 8 - j; h++) {
  81.                     MAIN();
  82.                 }
  83.             }
  84.         }
  85.     } 
  87.     work();
  88.         OUTS();
  90.     return 0;
  91.         //AKIOI
  93. }

H tiandaochouqin

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4. const int maxn=1e6+2;
  5. stack<int>s;
  6. ll ans,sum[maxn],l[maxn],r[maxn];
  7. vector<int>v[maxn];
  8. int a[maxn];
  9. int query(ll x,int l,int r)
  10. {
  11.     return upper_bound(v[x].begin(),v[x].end(),r)-lower_bound(v[x].begin(),v[x].end(),l);
  12. }
  13. void slove()
  14. {
  15.     int n,k; 
  16.     scanf("%d %d",&n,&k);
  17.     v[0].push_back(0);
  18.     for(int i=1;i<=n;++i) {
  19.         scanf("%d",&a[i]);
  20.         sum[i]=(sum[i-1]+a[i])%k;
  21.         v[sum[i]].push_back(i);
  22.     }
  23.     a[n+1]=1e9+7;
  24.     s.push(0);
  25.     for(int i=1;i<=n;++i)
  26.     {
  27.         while(s.size()>1&&a[s.top()]<a[i]) s.pop();
  28.         l[i]=s.top();
  29.         s.push(i);
  30.     }
  31.     while(!s.empty()) s.pop();
  32.     s.push(n+1);
  33.     for(int i=n;i>=1;--i)
  34.     {
  35.         while(s.size()>1&&a[s.top()]<=a[i]) s.pop();
  36.         r[i]=s.top();
  37.         s.push(i);
  38.     }
  39.     for(int i=1;i<=n;++i) a[i]%=k;
  40.     for(int i=1;i<=n;++i)
  41.     if(i-l[i]<r[i]-i)
  42.     for(int j=l[i]+1;j<=i;++j) ans+=query((sum[j-1]+a[i])%k,i,r[i]-1);
  43.     else for(int j=i;j<r[i];++j) ans+=query((sum[j]-a[i]+k)%k,l[i],i-1);
  44.     printf("%lld\n",ans-n);
  45. }
  46. int main()
  47. {
  48.     slove();
  49. }

I

J yangzijiangac

  1. #include <cstdio>
  2. #include <algorithm>
  3. #include <vector>
  4. #include <iostream>
  5. #include <map>
  6. #include <queue>
  7. #include <cstring>
  8. #include <string>
  9. #include <cstdlib>
  10. #include <cmath>
  11. #include <set>
  12. using namespace std;
  13. const int inf = (1 << 30);
  14. typedef long long ll;
  15. const int maxn = 1e6 + 5;
  16. vector<int> vec;
  17. struct node
  18. {
  19.     int ls, rs, w;
  20.     int size, fact;
  21.     bool exist;
  22. } tr[maxn];
  23. int cnt, rt;
  24. void newnode(int &now, int w)
  25. {
  26.     now = ++cnt;
  27.     tr[now].w = w, tr[now].size = tr[now].fact = 1;
  28.     tr[now].exist = true;
  29. }
  30. void pushup(int now)
  31. {
  32.     tr[now].size = tr[tr[now].ls].size + tr[tr[now].rs].size + 1;
  33. }
  34. void pushfp(int now)
  35. {
  36.     tr[now].fact = tr[tr[now].ls].fact + tr[tr[now].rs].fact + 1;
  37. }
  38. bool judge(int now)
  39. {
  40.     if (max(tr[tr[now].ls].size, tr[tr[now].rs].size) > (tr[now].size * 0.75))
  41.         return true;
  42.     if (tr[now].size - tr[now].fact > tr[now].size * 0.3)
  43.         return true;
  44.     return false;
  45. }
  46. void ldm(int now)
  47. {
  48.     if (!now)
  49.         return;
  50.     ldm(tr[now].ls);
  51.     vec.push_back(now);
  52.     ldm(tr[now].rs);
  53. }
  54. void cre(int &now, int L, int R)
  55. {
  56.     if (L == R)
  57.     {
  58.         now = vec[L];
  59.         tr[now].ls = tr[now].rs = 0;
  60.         tr[now].size = tr[now].fact = 1;
  61.         return;
  62.     }
  63.     int mid = L + R >> 1;
  64.     while (tr[vec[mid]].w == tr[vec[mid - 1]].w)
  65.         mid--;
  66.     now = vec[mid];
  67.     if (L < mid)
  68.         cre(tr[now].ls, L, mid - 1);
  69. }
  70. void rebuild(int &now)
  71. {
  72. }
  73. void update(int now, int en)
  74. {
  75.     if (now == en)
  76.         return;
  77.     if (tr[now].w > tr[en].w)
  78.         update(tr[now].ls, en);
  79.     else
  80.         update(tr[now].rs, en);
  81.     pushup(now);
  82. }
  83. void check(int &now, int en)
  84. {
  85.     if (now == en)
  86.         return;
  87.     if (judge(now))
  88.     {
  89.         rebuild(now);
  90.         update(rt, now);
  91.         return;
  92.     }
  93.     if (tr[now].w > tr[en].w)
  94.         check(tr[now].ls, en);
  95.     else
  96.         check(tr[now].rs, en);
  97. }
  98. void inser(int &now, int w)
  99. {
  100.     if (!now)
  101.     {
  102.         newnode(now, w);
  103.         check(rt, now);
  104.         return;
  105.     }
  106.     tr[now].size++, tr[now].fact++;
  107.     if (w < tr[now].w)
  108.         inser(tr[now].ls, w);
  109.     else
  110.         inser(tr[now].rs, w);
  111. }
  112. void dele(int now, int w)
  113. {
  114.     if (tr[now].exist && tr[now].w == w)
  115.     {
  116.         tr[now].exist = false;
  117.         tr[now].fact--;
  118.         check(rt, now);
  119.         return;
  120.     }
  121.     tr[now].fact--;
  122.     if (w < tr[now].w)
  123.         dele(tr[now].ls, w);
  124.     else
  125.         dele(tr[now].rs, w);
  126. }
  127. int a[maxn], b[maxn], sum[maxn];
  128. ll gcd(ll a, ll b)
  129. {
  130.     if (b == 0)
  131.         return a;
  132.     return gcd(b, a % b);
  133. }
  135. ll ext_gcd(ll &a, ll &b, ll n, ll m)
  136. {
  137.     if (m == 0)
  138.     {
  139.         a = 1;
  140.         b = 0;
  141.         return n;
  142.     }
  143.     ll d = ext_gcd(b, a, m, n % m);
  144.     b -= n / m * a;
  145.     return d;
  146. }
  147. int main()
  148. {
  149.     ios::sync_with_stdio(false);
  150.     cin.tie(0);
  151.     ll a, b, c;
  152.     while (cin >> a >> b >> c)
  153.     {
  154.         if (!a && !b)
  155.         {
  156.             if (!c)
  157.                 cout << "YES" << endl;
  158.             else
  159.                 cout << "NO" << endl;
  160.         }
  161.         else if (!a)
  162.         {
  163.             if ((c % b) == 0)
  164.                 cout << "YES" << endl;
  165.             else
  166.                 cout << "NO" << endl;
  167.         }
  168.         else if (!b)
  169.         {
  170.             if ((c % a) == 0)
  171.                 cout << "YES" << endl;
  172.             else
  173.                 cout << "NO" << endl;
  174.         }
  175.         else
  176.         {
  177.             ll x, y, g;
  178.             g = ext_gcd(x, y, a, b);
  179.             if ((c % g) != 0)
  180.             {
  181.                 cout << "NO" << endl;
  182.                 continue;
  183.             }
  184.             ll x0 = b / g;
  185.             ll y0 = a / g;
  186.             x = ((c / g % x0) * (x % x0) % x0 + x0) % x0;
  187.             y = (c - x * a) / b;
  188.             bool fla = false;
  189.             while (y > 0)
  190.             {
  191.                 if (gcd(x, y) == 1)
  192.                 {
  193.                     fla = true;
  194.                     break;
  195.                 }
  196.                 x += x0;
  197.                 y -= y0;
  198.             }
  199.             if (fla)
  200.                 cout << "YES" << endl;
  201.             else
  202.                 cout << "NO" << endl;
  203.         }
  204.     }
  205. }

K tiandaochouqin

  1. #include <bits/stdc++.h>
  2. const int maxn=700;
  3. using namespace std;
  4. char s[maxn];
  5. int tot=0,p[maxn],h[maxn],g[maxn][maxn],vis[maxn],sum[maxn];
  6. double d[maxn];
  7. vector<int>v[maxn],v1;
  8. int turn(char a,char b)
  9. {
  10.     return (a-'a')*26+(b-'a')+1;
  11. }
  12. bool spfa(int s,double mid)
  13. {
  14.     queue<int>q;
  15.     for(int i=0;i<maxn;++i) vis[i]=d[i]=sum[i]=0;
  16.     q.push(s);
  17.     vis[s]=sum[s]=1;
  18.     while(!q.empty())
  19.     {
  20.         int top=q.front();
  21.         q.pop();
  22.         vis[top]=0;
  23.         for(int t:v[top])
  24.         {
  25.             double x=g[top][t]-mid;
  26.             if(d[top]+x>d[t])
  27.             {
  28.                 d[t]=d[top]+x;
  29.                 if(!vis[t])
  30.                 {
  31.                     sum[t]++;
  32.                     if(sum[t]>tot) return true;
  33.                     q.push(t);
  34.                     vis[t]=1;
  35.                 }
  36.             }
  37.         }
  38.     }
  39.     return false;
  40. }
  41. int check(double mid)
  42. {
  43.     for(int i:v1)
  44.     if(spfa(i,mid)) return 1;
  45.     return 0;
  46. }
  47. int main()
  48. {
  49.     int n;
  50.     while(scanf("%d",&n)!=EOF)
  51.     {
  52.         if(n==0) break;
  53.         v1.clear();
  54.         tot=0;
  55.         for(int i=0;i<maxn;++i) v[i].clear(),p[i]=h[i]=0;
  56.         for(int i=0;i<maxn;++i) for(int j=0;j<maxn;++j) g[i][j]=0;
  57.         for(int i=1;i<=n;++i)
  58.         {
  59.             scanf("%s",s+1);
  60.             int len=strlen(s+1);
  61.             if(len<2) continue;
  62.             int x=turn(s[1],s[2]),y=turn(s[len-1],s[len]);
  63.             if(!g[x][y]) v[x].push_back(y);//存图 
  64.             g[x][y]=max(g[x][y],len);//存边权 
  65.             if(!p[x]) v1.push_back(x);//记录起点 
  66.             p[x]=1;
  67.             if(!h[x]) tot++;//记录点的总数 
  68.             if(!h[y]) tot++;
  69.             h[x]=h[y]=1;
  70.         }
  71.         double l=0,r=1000,mid;
  72.         while(r-l>1e-3)
  73.         {
  74.             mid=(l+r)/2;
  75.             if(check(mid)) l=mid;
  76.             else r=mid;
  77.          } 
  78.          if(l<1e-6) printf("No solution.\n");
  79.     else printf("%.2lf\n",l);
  80.     }
  81. }

L

M _Wallace_

  1. /******************************
  2. 非正式参赛选手 
  3. please skip it. 
  4. ******************************/
  5. #include <iostream>
  6. #include <algorithm>
  8. using namespace std;
  9. const int N = 2e5 + 5;
  11. int ch[N][2], fa[N], size[N];
  12. bool rev[N];
  14. #define lc ch[x][0]
  15. #define rc ch[x][1]
  17. inline void pushup(int x) {
  18.     size[x] = size[lc] + size[rc] + 1;
  19. }
  20. inline void setRev(int x) {
  21.     swap(lc, rc), rev[x] ^= 1;
  22. }
  23. inline void pushdown(int x) {
  24.     if (rev[x]) {
  25.         if (lc) setRev(lc);
  26.         if (rc) setRev(rc);
  27.         rev[x] = 0;
  28.     }
  29. }
  31. inline bool isRoot(int x) {
  32.     return x != ch[fa[x]][0] && x != ch[fa[x]][1];
  33. }
  34. inline int getc(int x) {
  35.     return x == ch[fa[x]][1];
  36. }
  38. inline void rotate(int x) {
  39.     int y = fa[x], z = fa[y];
  40.     int k = getc(x), w = ch[x][!k];
  41.     if (!isRoot(y)) ch[z][getc(y)] = x;
  42.     ch[x][!k] = y, ch[y][k] = w;
  43.     if (w) fa[w] = y;
  44.     fa[y] = x, fa[x] = z, pushup(y);
  45. }
  46. inline void pushdownAll(int x) {
  47.     if (!isRoot(x)) pushdownAll(fa[x]);
  48.     pushdown(x);
  49. }
  50. inline void splay(int x) {
  51.     pushdownAll(x);
  52.     for (register int y = fa[x]; !isRoot(x); rotate(x), y = fa[x])
  53.         if (!isRoot(y)) rotate(getc(x) != getc(y) ? x : y);
  54.     pushup(x);
  55. }
  57. inline void access(int x) {
  58.     for (register int y = 0; x; x = fa[y = x])
  59.         splay(x), rc = y, pushup(x);
  60. }
  61. inline void makeRoot(int x) {
  62.     access(x), splay(x), setRev(x);
  63. }
  64. inline void split(int x, int y) {
  65.     makeRoot(x), access(y), splay(y);
  66. }
  67. inline int findRoot(int x) {
  68.     access(x), splay(x), pushdown(x);
  69.     while (lc) pushdown(x = lc);
  70.     return splay(x), x;
  71. }
  72. inline void link(int x, int y) {
  73.     if (makeRoot(x), findRoot(y) != x) fa[x] = y;
  74. }
  75. inline void cut(int x, int y) {
  76.     makeRoot(x);
  77.     if (findRoot(y) == x && fa[y] == x && !ch[y][0])
  78.         fa[y] = rc = 0, pushup(x);
  79. }
  81. int n, q;
  82. inline int getPre() {
  83.     int x = ch[n + 1][0];
  84.     while (pushdown(x), rc) x = rc;
  85.     return x;
  86. }
  88. int nxt[N];
  89. signed main() {
  90.     ios::sync_with_stdio(false);
  91.     cin >> n >> q;
  93.     for (register int i = 1; i <= n + 1; i++)
  94.         size[i] = 1;
  95.     for (register int x, i = 1; i <= n; i++) {
  96.         cin >> nxt[i], x = nxt[i];
  97.         if (i + x <= n) link(i, i + x);
  98.         else link(i, n + 1);
  99.     }
  101.     for (; q; --q) {
  102.         int cmd, pos, val;
  103.         cin >> cmd >> pos;
  105.         if (cmd == 1) {
  106.             split(pos, n + 1);
  107.             cout << getPre() << ' ';
  108.             cout << size[n + 1] - 1 << endl;
  109.         } else {
  110.             cin >> val;
  111.             cut(pos, pos + nxt[pos] <= n ? pos + nxt[pos] : n + 1);
  112.             link(pos, pos + val <= n ? pos + val : n + 1);
  113.             nxt[pos] = val;
  114.         }
  115.     }
  116. }
添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注