[关闭]
@baobaobear 2020-03-29T10:50:15.000000Z 字数 9852 阅读 235

Contest 21

contest

A nznd

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4. const int N=100010;
  6. int main()
  7. {
  8.       int n;
  9.       while(cin >> n)
  10.       {
  11.           int k=sqrt(n);
  12.           if(k*k==n)cout << 1 << endl;
  13.           else cout << 0 << endl;
  14.       }
  15.     return 0;
  16. }

B lnkkerst

  1. #include <iostream>
  2. using namespace std;
  4. int n, a[200010];
  6. int main() {
  7.     cin >> n;
  8.     int now = 1;
  9.     if(!(n & 1)) {
  10.         puts("NO");
  11.         return 0;
  12.     }
  13.     for(int i = 1; i <= n * 2; i += 2) {
  14.         a[now] = i;
  15.         if(now <= n) {
  16.             a[now + n] = i + 1;
  17.             now = now + n + 1;
  18.         }
  19.         else {
  20.             a[now - n] = i + 1;
  21.             now = now - n + 1;
  22.         }
  23.     }
  24.     puts("YES");
  25.     for(int i = 1; i <= n * 2; ++i)
  26.         cout << a[i] << ' ';
  27.     return 0;
  28. }

C lnkkerst

  1. #include <iostream>
  2. #define int long long 
  3. using namespace std;
  5. signed main() {
  6.     int t;
  7.     cin >> t;
  8.     while(t--) {
  9.         int x;
  10.         cin >> x;
  11.         cout << x * (9 * x - 7) / 2 + 1 << endl;
  12.     }
  13.     return 0;
  14. }

D chromer

  1. import java.util.Scanner;
  2. public class Main
  3. {
  4.         public static void main(String args[]) throws Exception
  5.         {
  6.                 Scanner cin=new Scanner(System.in);
  7.                 int n,k;
  8.                 long r,s,p,sum=0;
  9.                 String str;
  10.                 char ch[]=new char[200050];
  11.                 n=cin.nextInt();
  12.                 k=cin.nextInt();
  13.                 r=cin.nextInt();
  14.                 s=cin.nextInt();
  15.                 p=cin.nextInt();
  16.                 str=cin.next();
  17.                 cin.close();
  18.                 for(int i=0; i<k; ++i) {
  19.                     if(str.charAt(i)=='r') {
  20.                         sum+=p;
  21.                         ch[i]='p';
  22.                     }
  23.                     if(str.charAt(i)=='s') {
  24.                         sum+=r;
  25.                         ch[i]='r';
  26.                     }
  27.                     if(str.charAt(i)=='p') {
  28.                         sum+=s;
  29.                         ch[i]='s';
  30.                     }
  31.                 }
  32.                 for(int i=k; i<n-k; ++i) {
  33.                     if(str.charAt(i)=='r') {
  34.                         if(ch[i-k]=='p') {
  35.                             if(str.charAt(i+k)=='s')
  36.                                 ch[i]='s';
  37.                             if(str.charAt(i+k)=='r')
  38.                                 ch[i]='r';
  39.                             if(str.charAt(i+k)=='p')
  40.                                 ch[i]='r';
  41.                         }
  42.                         else {
  43.                             sum+=p;
  44.                             ch[i]='p';
  45.                         }
  46.                     }
  47.                     if(str.charAt(i)=='s') {
  48.                         if(ch[i-k]=='r') {
  49.                             if(str.charAt(i+k)=='s')
  50.                                 ch[i]='s';
  51.                             if(str.charAt(i+k)=='r')
  52.                                 ch[i]='s';
  53.                             if(str.charAt(i+k)=='p')
  54.                                 ch[i]='p';
  55.                         }
  56.                         else {
  57.                             sum+=r;
  58.                             ch[i]='r';
  59.                         }
  60.                     }
  61.                     if(str.charAt(i)=='p') {
  62.                         if(ch[i-k]=='s') {
  63.                             if(str.charAt(i+k)=='s')
  64.                                 ch[i]='p';
  65.                             if(str.charAt(i+k)=='r')
  66.                                 ch[i]='r';
  67.                             if(str.charAt(i+k)=='p')
  68.                                 ch[i]='r';
  69.                         }
  70.                         else {
  71.                             sum+=s;
  72.                             ch[i]='s';
  73.                         }
  74.                     }
  75.                 }
  76.                 int pppp;
  77.                 if(n-k<k)pppp=k;
  78.                 else pppp=n-k;
  79.                 for(int i=pppp; i<n; ++i) {
  80.                     if(str.charAt(i)=='r') {
  81.                         if(i-k<0)
  82.                             sum+=p;
  83.                         else if(ch[i-k]!='p')
  84.                             sum+=p;
  85.                     }
  86.                     if(str.charAt(i)=='s') {
  87.                         if(i-k<0)
  88.                             sum+=r;
  89.                         else if(ch[i-k]!='r')
  90.                             sum+=r;
  91.                     }
  92.                     if(str.charAt(i)=='p') {
  93.                         if(i-k<0)
  94.                             sum+=s;
  95.                         else if(ch[i-k]!='s')
  96.                             sum+=s;
  97.                     }
  98.                 }
  99.                 System.out.println(sum);
  100.         }
  101. }

E chromer

  1. import java.util.Arrays;
  2. import java.util.Scanner;
  3. public class Main
  4. {
  5.         public static void main(String args[]) throws Exception
  6.         {
  7.                 Scanner cin=new Scanner(System.in);
  8.                 int n,midmid,ll,rr;
  9.                 long sum,l,r,mid,k;
  10.                 n=cin.nextInt();
  11.                 k=cin.nextLong();
  12.                 long arr[]=new long[n];
  13.                 for(int i=0; i<n; ++i) {
  14.                     arr[i]=cin.nextLong();
  15.                 }
  16.                 Arrays.sort(arr);
  17.                 if(arr[0]<=0&&arr[n-1]<=0) {
  18.                     //l=arr[n-1]*arr[n-2];
  19.                     //r=arr[0]*arr[1];
  20.                     l=-1;r=1;
  21.                     for(int i=0; i<18; ++i) {
  22.                         l*=(long)10;
  23.                         r*=(long)10;
  24.                     }
  25.                     --l;++r;
  26.                     --l;++r;
  27.                     --l;++r;
  28.                 }
  29.                 else if(arr[0]>=0&&arr[n-1]>=0) {
  30.                     //l=arr[0]*arr[1];
  31.                     //r=arr[n-1]*arr[n-2];
  32.                     l=-1;r=1;
  33.                     for(int i=0; i<18; ++i) {
  34.                         l*=(long)10;
  35.                         r*=(long)10;
  36.                     }
  37.                     --l;++r;
  38.                     --l;++r;
  39.                     --l;++r;
  40.                 }
  41.                 else {
  42.                     l=-1;r=1;
  43.                     for(int i=0; i<18; ++i) {
  44.                         l*=(long)10;
  45.                         r*=(long)10;
  46.                     }
  47.                     --l;++r;
  48.                     --l;++r;
  49.                     --l;++r;
  50.                 }
  51.                 while(true) {
  52.                     if(r-l<=1)
  53.                         break;
  54.                     mid=(l+r)/2;
  55.                     sum=0;
  56.                     for(int i=0; i<n; ++i) {
  57.                         ll=i;
  58.                         rr=n;
  59.                         if(arr[i]<0){
  60.                             while(rr-ll>1){
  61.                                 midmid=(ll+rr)/2;
  62.                                 if(arr[i]*arr[midmid]<=mid)
  63.                                     rr=midmid;
  64.                                 else 
  65.                                     ll=midmid;
  66.                             }
  67.                             sum=sum+(long)(n-rr);
  68.                         }
  69.                         else {
  70.                             while(rr-ll>1){
  71.                                 midmid=(ll+rr)/2;
  72.                                 if(arr[i]*arr[midmid]<=mid)
  73.                                     ll=midmid;
  74.                                 else 
  75.                                     rr=midmid;
  76.                             }
  77.                             sum=sum+(long)(ll-i);
  78.                         }
  79.                     }
  80.                     if(sum<k)
  81.                         l=mid;
  82.                     else
  83.                         r=mid;
  84.                 }
  85.                 System.out.println(r);
  86.                 cin.close();
  87.         }
  88. }

F 15291200127

  1. #include <set>
  2. #include <map>
  3. #include <deque>
  4. #include <queue>
  5. #include <stack>
  6. #include <cmath>
  7. #include <ctime>
  8. #include <bitset>
  9. #include <cstdio>
  10. #include <string>
  11. #include <vector>
  12. #include <cstdlib>
  13. #include <cstring>
  14. #include <cassert>
  15. #include <iostream>
  16. #include <algorithm>
  17. #define mem(a,b) memset(a,b,sizeof (a))
  18. #define gcd(a,b) __gcd(a,b)
  19. #define all(a) a.begin(),a.end()
  20. #define in(a) insert(a)
  21. #define sz() size()
  22. #define endl '\n'
  23. #define pb push_back
  24. typedef unsigned long long ll;
  25. const int maxn=100010;
  26. const int inf=1e9;
  27. const ll mod=998244353;
  28. const double pi=3.14159265358979;
  29. const double ep=0.0;
  30. using namespace std;
  31. int main()
  32. {
  33.     string s;
  34.     int k,ans=0;
  35.     cin>>s>>k;
  36.     int n=s.sz();
  37.     if (n>1)
  38.     {
  39.         if (k==1)
  40.             ans+=(n-1)*9;
  41.         else if (k==2)
  42.             ans+=(n-1)*(n-2)/2*9*9;
  43.         else
  44.             ans+=(n-1)*(n-2)*(n-3)/6*9*9*9;
  45.     }
  46.     if (k==1)
  47.         ans+=s[0]-'0';
  48.     if (k==2)
  49.     {
  50.         ans+=(s[0]-'1')*(n-1)*9;
  51.         s.erase(0,1);
  52.         n--;
  53.         while (s[0]=='0')
  54.         {
  55.             s.erase(0,1);
  56.             n--;
  57.         }
  58.         if (n>=1)
  59.         {
  60.             ans+=(n-1)*9;
  61.             ans+=(s[0]-'0');
  62.         }
  63.     }
  64.     if (k==3)
  65.     {
  66.         ans+=(s[0]-'1')*(n-1)*(n-2)/2*9*9;
  67.         s.erase(0,1);
  68.         n--;
  69.         while (s[0]=='0')
  70.         {
  71.             s.erase(0,1);
  72.             n--;
  73.         }
  74.         if (n>1)
  75.         {
  76.             ans+=(n-1)*(n-2)/2*9*9;
  77.             ans+=(s[0]-'1')*(n-1)*9;
  78.             s.erase(0,1);
  79.             n--;
  80.             while (s[0]=='0')
  81.             {
  82.                 s.erase(0,1);
  83.                 n--;
  84.             }
  85.             if (n>=1)
  86.             {
  87.                 ans+=(n-1)*9;
  88.                 ans+=(s[0]-'0');
  89.             }
  90.         }
  91.     }
  92.     cout<<ans<<endl;
  93.     return 0;
  94. }

G chenyingqi

  1. #include <iostream>
  2. #include <cstdio>
  3. #include <fstream>
  4. #include <algorithm>
  5. #include <cmath>
  6. #include <deque>
  7. #include <vector>
  8. #include <queue>
  9. #include <string>
  10. #include <cstring>
  11. #include <map>
  12. #include <stack>
  13. #include <set>
  14. #include <sstream>
  15. #define IOS ios_base::sync_with_stdio(0); cin.tie(0);
  16. #define ll long long
  17. #define INF 0x3f3f3f3f 
  18. #define MEM(x,y) memset(x,y,sizeof(x))
  19. #define int long long
  20. #define rep(i , a , b) for(int i = a ; i <= b ; i ++)
  21. #define P pair<int,int>
  22. #define  sc(a) scanf("%lld",&a)
  23. #define pf(a) printf("%lld ",a)
  24. using namespace std;
  25. const int maxn = 1 << 16;
  26. struct node
  27. {
  28.     int p1;
  29.     int d1;
  30.     bool operator<(const struct node& a1)const
  31.     {
  32.         return d1 > a1.d1;
  33.     }
  34. };
  35. int du[16];
  36. int eg[16][16];
  37. int d[maxn];
  38. bool vis[maxn];
  39. int n, m, s, ed, fir;
  40. void dijkstra()
  41. {
  42.     priority_queue<node> que;
  43.     for (int i = 0; i < (1<<n); i++)
  44.     {
  45.         d[i] = -1;
  46.         vis[i] = false;
  47.     }
  48.     d[s] = fir;
  49.     node n1;
  50.     n1.p1 = s;
  51.     n1.d1 = d[s];
  52.     que.push(n1);
  53.     while (!que.empty())
  54.     {
  55.         node ans = que.top();
  56.         que.pop();
  57.        int u = ans.p1;
  58.         if (vis[u]) continue;
  59.         vis[u] = true;
  60.         if (u == ed) break;
  61.         for (int i = 0; i < n; i++)
  62.         {
  63.             for (int j = 0; j < i; j++)
  64.             {
  65.                 if (eg[i][j] != -1)
  66.                 {
  67.                     int v = u ^ (1 << i);
  68.                     v = v ^ (1 << j);
  69.                     if (d[v] == -1 || d[u] + eg[i][j] < d[v])
  70.                     {
  71.                         d[v] = d[u] + eg[i][j];
  72.                         node n2;
  73.                         n1.p1 = v;
  74.                         n1.d1 = d[v];
  75.                         que.push(n1);
  77.                     }
  78.                 }
  79.             }
  80.         }
  81.     }
  82. }
  83. signed main()
  84. {
  85.     while (scanf("%d", &n) != EOF && n)
  86.     {
  87.         sc(m);
  88.         rep(i, 0, n - 1)
  89.         {
  90.             du[i] = 0;
  91.             rep(j, 0, n - 1)
  92.                 eg[i][j] = -1;
  93.         }
  94.         fir = 0;
  95.         int q, w, e;
  96.         rep(i, 0, m - 1)
  97.         {
  98.             cin >> q >> w >> e;
  99.             du[q]++;
  100.             du[w]++;
  101.             fir += e;
  102.             if (eg[q][w] == -1 || eg[q][w] > e)
  103.                 eg[q][w] = eg[w][q] = e;
  104.         }
  105.         s = 0;
  106.         rep(i, 0, n - 1)
  107.         {
  108.             ed = ed | (1 << i);
  109.             if (du[i] % 2 == 0)
  110.                 s = s | (1 << i);
  111.         }
  112.         dijkstra();
  113.         cout << d[ed] << endl;
  114.     }
  116.     return 0;
  118. }

H onlyRP

  1. /**
  2.  *　　　　　　  　　┏┓　　 　┏┓
  3.  * 　　　　　  　　┏┛┗━━━━━━━┛┗━━━┓
  4.  * 　　　　　  　　┃　　　　　　　┃ 　
  5.  * 　　　　　  　　┃　　　━　　 　┃
  6.  * 　　　　　  　　┃　＞　　　＜　┃
  7.  * 　　　　　  　　┃　　　　　　　┃
  8.  * 　　　　　  　　┃...　⌒　... 　┃
  9.  * 　　　　　　  　┃              ┃
  10.  * 　　　　　　  　┗━┓          ┏━┛
  11.  * 　　　　　　　　　┃          ┃　Code is far away from bug with the animal protecting　　　　　　　　　　
  12.  * 　　　　　　　　　┃          ┃   神兽保佑,代码无bug
  13.  * 　　　　　　　　　┃          ┃　　　　　　　　　　　
  14.  * 　　　　　　　　　┃          ┃  　　　　　　
  15.  * 　　　　　　　　　┃          ┃
  16.  * 　　　　　　　　　┃          ┃　　　　　　　　　　　
  17.  * 　　　　　　　　　┃          ┗━━━┓
  18.  * 　　　　　　　　　┃              ┣┓
  19.  * 　　　　　　　　　┃              ┏┛
  20.  * 　　　　　　　　　┗┓┓┏━━━━━━━━┳┓┏┛
  21.  * 　　　　　　　　　　┃┫┫       ┃┫┫
  22.  * 　　　　　　　　　　┗┻┛       ┗┻┛
  23.  */ 
  24. #include<cstdio>
  25. #include<cstring>
  26. #include<algorithm>
  27. #include<iostream>
  28. #include<queue>
  29. #include<map>
  30. #include<stack>
  31. #include<cmath>
  32. #include<set>
  33. #include<bitset>
  34. #include<complex>
  35. #include<assert.h>
  36. #define inc(i,l,r) for(int i=l;i<=r;i++)
  37. #define dec(i,l,r) for(int i=l;i>=r;i--)
  38. #define link(x) for(edge *j=h[x];j;j=j->next)
  39. #define mem(a) memset(a,0,sizeof(a))
  40. #define ll long long
  41. #define eps 1e-8
  42. #define succ(x) (1<<x)
  43. #define mid (x+y>>1)
  44. #define lowbit(x) (x&(-x))
  45. #define sqr(x) (1ll*(x)*(x))
  46. #define NM 100005 
  47. #define nm 200005
  48. using namespace std;
  49. const double pi=acos(-1);
  50. const int inf=2e9+7;
  51. ll read(){
  52.     ll x=0,f=1;char ch=getchar();
  53.     while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
  54.     while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
  55.     return f*x;
  56. }
  60. int n,a[NM],c[NM],s;
  62. int main(){
  63.     n=read();
  64.     inc(i,1,n)scanf("%1d",a+i);
  65.     c[n+1]=n+1;
  66.     dec(i,n,1)if(a[i]==1)c[i]=c[i+1];else c[i]=i;
  67.     inc(i,1,n){
  68.     int t=1;
  69.     inc(j,i,n){
  70.         t=t*a[j];
  71.         if(t>n)break;
  72.         if(c[j+1]-i+1>t&&j-i+1<=t)s++;
  73.         j=c[j+1]-1;
  74.     }
  75.     }
  76.     printf("%d\n",s);
  77.     return 0;
  78. }

I djddskkekk

  1. #include <iostream>
  2. #include <vector>
  3. #include <string>
  4. #include <algorithm>
  5. #include <cstdio>
  6. #include <cstring>
  7. #include <cmath>
  8. using namespace std;
  11. int n;
  12. long long s, r;
  14. int main ( void )
  15. {
  16.     ios::sync_with_stdio(false);
  17.     cin.tie(0);   
  18.     cin >> n;
  19.     vector < long long > a ( n );
  20.     for ( int i = 0 ; i < n ; i++ ) {
  21.         cin >> a [ i ];
  22.         s ^= a [ i ];
  23.     } //前缀 
  24.     int number = 0;
  25.     for ( int k = 60 - 1 ; k >= 0 ; k--) {
  26.         long long l = 1LL << k; //long long int 
  27.         if ( s & l ) continue;//比较i位上面的为1的是奇数还是偶数，奇数忽略，因为无论怎么划分两部分异或和在i位上都是一个1一个0 
  28.         for ( int i = number ; i < n; i++ ) {
  29.             if ( a [ i ] & l ) { //考虑偶数个1位如何构造最大,高位比低位重要 
  30.                 long long t = a [ i ];
  31.                 for ( int j = i + 1 ; j < n ; j++ ) {
  32.                     if ( a [ j ] & l ) {
  33.                         a [ j ] ^= t;
  34.                     }
  35.                 }
  36.                 swap ( a [ number++ ] , a [ i ] );//a [ i ]用过了 
  37.                 if ( !( r & l ) ) r ^= t;
  38.                 break;
  39.             }
  40.         }
  41.     }
  42.     //r构造了一个能为1就为1的数
  43.     s = r ^ s;
  44.     r = s + r;
  45.     cout << r << endl;
  47.     return 0;
  48. }

J 15291200127

  1. #include <set>
  2. #include <map>
  3. #include <deque>
  4. #include <queue>
  5. #include <stack>
  6. #include <cmath>
  7. #include <ctime>
  8. #include <bitset>
  9. #include <cstdio>
  10. #include <string>
  11. #include <vector>
  12. #include <cstdlib>
  13. #include <cstring>
  14. #include <cassert>
  15. #include <iostream>
  16. #include <algorithm>
  17. #define mem(a,b) memset(a,b,sizeof (a))
  18. #define gcd(a,b) __gcd(a,b)
  19. #define all(a) a.begin(),a.end()
  20. #define in(a) insert(a)
  21. #define sz() size()
  22. #define endl '\n'
  23. #define pb push_back
  24. using namespace std;
  25. typedef unsigned long long ll;
  26. const int maxn=100010;
  27. const int inf=1e9;
  28. const ll mod=998244353;
  29. const double pi=3.14159265358979;
  30. const double ep=0.0;
  31. struct A{
  32.     int l,r;
  33.     ll hashs;
  34. }tree[4*maxn];
  35. string ss;
  36. ll hh[maxn];
  37. ll chash()
  38. {
  39.     ll s=0;
  40.     for(int i=ss.sz()-1;i>=0;i--)
  41.         s=s*31+ss[i]-'a'+1;
  42.     return s;
  43. }
  44. void build(int L,int R,int id)
  45. {
  46.     tree[id].l=L;
  47.     tree[id].r=R;
  48.     if(L==R)
  49.     {
  50.         tree[id].hashs=ss[L]-'a'+1;
  51.         return;
  52.     }
  53.     int mid=(L+R)>>1;
  54.     build(L,mid,id<<1);
  55.     build(mid+1,R,id<<1|1);
  56.     tree[id].hashs=tree[id<<1].hashs+tree[id<<1|1].hashs*hh[mid+1-L];
  57. }
  58. void update(int l,int id)
  59. {
  60.     if(tree[id].l==tree[id].r)
  61.     {
  62.         tree[id].hashs=ss[l]-'a'+1;
  63.         return;
  64.     }
  65.     int mid=(tree[id].l+tree[id].r)>>1;
  66.     if(l<=mid)
  67.         update(l,id<<1);
  68.     else
  69.         update(l,id<<1|1);
  70.     tree[id].hashs=tree[id<<1].hashs+tree[id<<1|1].hashs*hh[mid+1-tree[id].l];
  71. }
  72. ll query(int L,int R,int id)
  73. {
  74.     if(tree[id].l>=L&&tree[id].r<=R)
  75.         return tree[id].hashs;
  76.     int mid=(tree[id].l+tree[id].r)>>1;
  77.     if(R<=mid)
  78.         return query(L,R,id<<1);
  79.     else if(L>mid)
  80.         return query(L,R,id<<1|1);
  81.     return query(L,mid,id<<1)+query(mid+1,R,id<<1|1)*hh[mid+1-L];
  82. }
  83. int main()
  84. {
  85.     map<ll,int>mp;
  86.     hh[0]=1;
  87.     for(int i=1;i<=maxn;i++)
  88.         hh[i]=hh[i-1]*31;
  89.     int t,k=1;
  90.     scanf("%d",&t);
  91.     while (t--)
  92.     {
  93.         printf("Case #%d:\n",k++);
  94.         int n;
  95.         scanf("%d",&n);
  96.         mp.clear();
  97.         for(int i=1;i<=n;i++)
  98.         {
  99.             cin>>ss;
  100.             mp.in(make_pair(chash(),1));
  101.         }
  102.         cin>>ss;
  103.         build(0,ss.sz()-1,1);
  104.         int q;
  105.         scanf("%d",&q);
  106.         while (q--)
  107.         {
  108.             int x;
  109.             char c;
  110.             cin>>c;
  111.             if(c=='C')
  112.             {
  113.                 cin>>x>>c;
  114.                 ss[x]=c;
  115.                 update(x,1);
  116.             }
  117.             else
  118.             {
  119.                 int l,r;
  120.                 cin>>l>>r;
  121.                 if(mp.find(query(l,r,1))!=mp.end())
  122.                     cout<<"Yes"<<endl;
  123.                 else
  124.                     cout<<"No"<<endl;
  125.             }
  126.         }
  127.     }
  128.     return 0;
  129. }

K djddskkekk

  1. #include <iostream>
  2. #include <cstdio>
  3. using namespace std;
  4. const int maxn = 200010;
  6. int n , a , b , c , front , behind;
  7. long long ans;
  8. int f [ maxn ] [ 2 ] , number_1 [ maxn ] , number_2 [ maxn ]; //一个维护边权为1，一个维护边权为0
  10. int find ( int x , int y ) {
  11.     if ( !f [ x ] [ y ] ) {
  12.         return x;
  13.     } else {
  14.         f [ x ] [ y ] = find ( f [ x ] [ y ] , y );
  15.         return f [ x ] [ y ];
  16.     }
  17. }
  18. int main ( void ) {
  19.     scanf ( "%d" , &n );
  20.     for ( int i = 1 ; i < n ; i++ ) {
  21.         scanf ( "%d %d %d" , &a , &b , &c );
  22.         front = find ( a , c ); 
  23.         behind = find ( b , c );//往前往后找联通的(其实就是两个方向搜）
  24.         if ( front != behind ) { 
  25.             f [ front ] [ c ] = behind;
  26.         }
  27.     }
  28.     for ( int i = 1 ; i <= n ; i++ ) { //这里把自己也算上了
  29.         number_1 [ find ( i , 1 ) ]++;
  30.         number_2 [ find ( i , 0 ) ]++;
  31.     }
  32.     for ( int i = 1 ; i <= n ; i++ ) { 
  33. //这里算了两部分，只有边权为1，只有边权为0，从0到1，只有边权为0和只有边权为1的，都是结点*（结点-1），如果是
  34. //联通的，就乘起来
  35. //要注意的问题是比如：
  36. /*
  37.         数据：
  38.         6
  39.         1 2 1
  40.         2 3 1
  41.         3 4 1
  42.         4 5 0
  43.         5 6 0
  44.         4是联通边权为1和边权为0的，在计算时把自己到自己的排除了，每一次计算都是如此，所以要减去1
  45. */
  46.         ans += 1ll * ( number_1 [ find ( i , 1 ) ] ) * ( number_2 [ find ( i , 0 ) ] ) - 1;
  47.     }
  48.     printf ( "%lld\n" , ans );
  49.     return 0;
  50. }
添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注