1 #include <iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #include<stdlib.h> 6 #include<vector> 7 #include<cmath> 8 #include<queue> 9 #include<set>10 using namespace std;11 #define N 10000012 #define LL long long13 #define INF 0xfffffff14 const double eps = 1e-8;15 const double pi = acos(-1.0);16 const double inf = ~0u>>2;17 int main()18 {19     int n,i,j;20     int ans = 0;21     cin>>n;22     for(i = 1; i <= n; i++)23     {24         int x,y;25         scanf("%d%d",&x,&y);26         if(y-x>=2) ans++;27     }28     cout<<ans<<endl;29     return 0;30 }

 1 #include <iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #include<stdlib.h> 6 #include<vector> 7 #include<cmath> 8 #include<queue> 9 #include<set>10 using namespace std;11 #define N 101012 #define LL long long13 #define INF 0xfffffff14 const double eps = 1e-8;15 const double pi = acos(-1.0);16 const double inf = ~0u>>2;17 int a[N];18 int fa[N];19 int r[N];20 int find(int x)21 {22     if(x!=fa[x])23     {24         fa[x] = find(fa[x]);25         return fa[x];26     }27     return x;28 }29 int main()30 {31     int n,m,k,i,j;32     cin>>n>>m>>k;33     for(i = 1 ;i <= m+1; i++) {fa[i] = i;r[i] = 1;}34     for(i = 1; i <= m+1; i++)35     scanf("%d",&a[i]);36     int ans = 0;37     for(i = 1 ; i <= m; i++)38     {39         int cnt = 0;40         for(int g = 0 ; g < n ;g++)41             if((a[m+1]&(1<<g))!=(a[i]&(1<<g))) cnt++;42             if(cnt<=k) ans++;43     }44 //    for(i = 1; i <= m+1; i++)45 //        for(j = 1; j <= m+1; j++)46 //        {47 //            if(i==j) continue;48 //            int cnt = 0;49 //            for(int g = 0 ; g < n ;g++)50 //            if((i&(1<<g))!=(i&(1<<g))) cnt++;51 //            if(cnt<=k)52 //            {53 //                int tx = find(i);54 //                int ty = find(j);55 //                if(tx!=ty)56 //                {57 //                    fa[tx] = ty;58 //                    r[tx]+=r[ty];59 //                }60 //            }61 //        }62 //    int kk = find(m+1);63     cout<<ans<<endl;64     return 0;65 }

 1 #include <iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #include<stdlib.h> 6 #include<vector> 7 #include<cmath> 8 #include<queue> 9 #include<set>10 using namespace std;11 #define N 501012 #define LL long long13 #define INF 0xfffffff14 const double eps = 1e-8;15 const double pi = acos(-1.0);16 const double inf = ~0u>>2;17 int a[N];18 LL dp[N][N];19 LL sum[N];20 int main()21 {22     int n,m,k,i,j;23     cin>>n>>m>>k;24     for(i = 1; i <= n;  i++)25     {26         scanf("%d",&a[i]);27         sum[i] = sum[i-1]+a[i];28     }29     for(i = m; i <= n ;i++)30     {31         for(j = 1; j <= k; j++)32         dp[i][j] = max(dp[i-m][j-1]+sum[i]-sum[i-m],dp[i-1][j]);33     }34     cout<<dp[n][k]<<endl;35     return 0;36 }

  1 #include <iostream>  2 #include<cstdio>  3 #include<cstring>  4 #include<algorithm>  5 #include<stdlib.h>  6 #include<vector>  7 #include<cmath>  8 #include<queue>  9 #include<set> 10 #include<map> 11 #include<stack> 12 using namespace std; 13 #define N 500010 14 #define M 500010 15 #define LL long long 16 #define INF 0xfffffff 17 const double eps = 1e-8; 18 const double pi = acos(-1.0); 19 const double inf = ~0u>>2; 20 struct node 21 { 22     int u,v,next,w; 23 } edge[M]; 24 int t,low[N],pre[N],sccno[N],head[N],scc,dep,vis[N],dis[N]; 25 int dd1[N],dd2[N]; 26 int dp[N]; 27 int num[N],de[N]; 28 vector<int>cd[N]; 29 void init() 30 { 31     t = 0; 32     memset(head,-1,sizeof(head)); 33 } 34 void add(int u,int v) 35 { 36     edge[t].u  =u; 37     edge[t].v = v; 38     edge[t].next = head[u]; 39     head[u] = t++; 40 } 41 stack<int>s; 42 void dfs(int u) 43 { 44     low[u] = pre[u] = ++dep; 45     s.push(u); 46     for(int i = head[u] ; i!=-1 ; i = edge[i].next) 47     { 48         int v = edge[i].v; 49         if(!pre[v]) 50         { 51             dfs(v); 52             low[u] = min(low[u],low[v]); 53         } 54         else if(!sccno[v]) 55             low[u] = min(low[u],pre[v]); 56     } 57     if(low[u]==pre[u]) 58     { 59         scc++; 60         int minz = INF,sum=INF; 61         for(;;) 62         { 63             int x = s.top(); 64             s.pop(); 65             if(minz>num[x]) 66             { 67                 minz = num[x]; 68                 sum = dp[x]; 69             } 70             else if(minz==num[x]) sum = min(dp[x],sum); 71             sccno[x] = scc; 72             if(x==u)break; 73         } 74         dd1[scc] = minz; 75         dd2[scc] = sum; 76  77     } 78 } 79 void find_scc(int n) 80 { 81     scc=0; 82     dep=0; 83     memset(low,0,sizeof(low)); 84     memset(pre,0,sizeof(pre)); 85     memset(sccno,0,sizeof(sccno)); 86     for(int i = 1; i <= n ; i++) 87         if(!pre[i]) 88             dfs(i); 89 } 90 map<string,int>f; 91 vector<int>ed[N]; 92 char s1[N],s2[N]; 93 int a[N]; 94 int judge(char *str) 95 { 96     int i,k; 97     k= strlen(str); 98     int cnt = 0; 99     for(i = 0 ; i < k; i++)100         if(str[i]==‘R‘)101             cnt++;102     return cnt;103 }104 int ddfs(int u)105 {106     int i,j;107     for(i = 0 ; i< ed[u].size() ; i++)108     {109         int v = ed[u][i];110         if(!vis[v])111         {112             vis[v] = 1;113             int ss = ddfs(v);114             if(dd1[u]>=ss)115             {116                 if(dd1[u]==ss)117                     dd2[u] = min(dd2[u],dd2[v]);118                 else dd2[u] = dd2[v];119                 dd1[u] = ss;120             }121         }122         else if(dd1[u]>=dd1[v])123         {124             if(dd1[u]==dd1[v]) dd2[u] = min(dd2[u],dd2[v]);125             else dd2[u] = dd2[v];126             dd1[u] = dd1[v];127         }128     }129     return dd1[u];130 }131 int main()132 {133     init();134     int m,i,j,n;135     scanf("%d",&m);136     int g = 0;137     for(i = 1; i <= m ; i++)138     {139         scanf("%s",s1);140         int len = strlen(s1);141         for(j = 0 ; j <  len; j++) if(s1[j]>=‘a‘&&s1[j]<=‘z‘) s1[j]-=32;142         if(!f[s1])143         {144             a[i] = ++g;145             f[s1] = g;146         }147         else a[i] = f[s1];148         num[a[i]] = judge(s1);149         dp[a[i]] = len;150     }151     scanf("%d",&n);152     for( i =1 ; i <= n ; i++)153     {154         int u,v;155         scanf("%s%s",s1,s2);156         int len1 =strlen(s1) ,len2 = strlen(s2);157         for(j = 0 ; j <  len1; j++) if(s1[j]>=‘a‘&&s1[j]<=‘z‘) s1[j]-=32;158         for(j = 0 ; j <  len2; j++) if(s2[j]>=‘a‘&&s2[j]<=‘z‘) s2[j]-=32;159         if(!f[s1])160         {161             u = ++g;162             f[s1] = g;163         }164         else u = f[s1];165         if(!f[s2])166         {167             v = ++g;168             f[s2] = g;169         }170         else v = f[s2];171         add(u,v);172         num[u] = judge(s1);173         num[v] = judge(s2);174         dp[u] = len1;175         dp[v] = len2;176         cd[u].push_back(v);177     }178     find_scc(g);179     for(i = 1 ; i <= g; i++)180     {181         int u = sccno[i];182         for(j = 0 ;j < cd[i].size() ; j++)183         {184             int v = sccno[cd[i][j]];185             if(v==u) continue;186             ed[u].push_back(v);187             de[v] = 1;188         }189     }190     memset(vis,0,sizeof(vis));191     for(i = 1 ; i <= scc; i++)192     {193         if(!de[i])194         {195             vis[i] = 1;196             ddfs(i);197         }198     }199     LL ans = 0,sum=0;200     for(i = 1 ; i<= m; i++)201     {202         int u = sccno[a[i]];203         //cout<<u<<" "<<dd2[u]<<endl;204         ans+=dd1[u];205         sum+=dd2[u];206     }207     cout<<ans<<" "<<sum<<endl;208     return 0;209 }