不会Java和高精度

unsolved

取最长的串跑AC自动机，跑过的点需要标记。

1 #include 
      
         2 #define Next next  3 using namespace std;  4 const int MAXN=1e5+5;  5 struct Trie  6 {  7     int vis[MAXN];  8     int next[MAXN][26],fail[MAXN],end[MAXN];  9     int root,L; 10     int newnode() 11     { 12         for(int i = 0;i < 26;i++) 13             next[L][i] = -1; 14         vis[L] = 0; 15         end[L++] = 0; 16         return L-1; 17     } 18     void init() 19     { 20         L = 0; 21         root = newnode(); 22     } 23     void insert(char buf[],int len) 24     { 25         int now = root; 26         for(int i = 0;i < len;i++) 27         { 28             if(next[now][buf[i]-'a'] == -1) 29                 next[now][buf[i]-'a'] = newnode(); 30             now = next[now][buf[i]-'a']; 31         } 32         end[now]++; 33     } 34     void build() 35     { 36         queue
       
        Q; 37         fail[root] = root; 38         for(int i = 0;i < 26;i++) 39             if(next[root][i] == -1) 40                 next[root][i] = root; 41             else 42             { 43                 fail[next[root][i]] = root; 44                 Q.push(next[root][i]); 45             } 46         while( !Q.empty() ) 47         { 48             int now = Q.front(); 49             Q.pop(); 50             for(int i = 0;i < 26;i++) 51                 if(next[now][i] == -1) 52                     next[now][i] = next[fail[now]][i]; 53                 else 54                 { 55                     fail[next[now][i]]=next[fail[now]][i]; 56                     Q.push(next[now][i]); 57                 } 58         } 59     } 60     int query(char buf[],int len) 61     { 62         int now = root; 63         int res = 0; 64         for(int i = 0;i < len;i++) 65         { 66             now = next[now][buf[i]-'a']; 67             int temp = now; 68             while( temp != root ) 69             { 70                 if(vis[temp]) break; 71                 vis[temp] = 1; 72                 res += end[temp]; 73                 end[temp] = 0; 74                 temp = fail[temp]; 75             } 76         } 77         return res; 78     } 79 }aho; 80  81 int n; 82 char tmp[MAXN]; 83 char str[MAXN]; 84 int main(){ 85     int t; 86     scanf("%d",&t); 87     while(t--){ 88         int Len=0; 89         aho.init(); 90         scanf("%d",&n); 91         for(int i=0;i
       
      

unsolved

unsolved

本原勾股三角形，所有边互质。

1.有m,n互质，并且异号，则（n*n+m*m, 2*n*m, n*n-m*m）组成一组本原勾股三角形。

2.Stern-Brocot Tree中能够构造出所有互质的数对。

跑一下Stern-Brocot Tree，然后计数，但是2.3e8有点慢，勉强卡过去

1 #include 
      
        2 using namespace std; 3  4 typedef long long LL; 5 const LL inf=1e9; 6  7 LL n; 8 LL a[(1<<18)]; 9 LL num[(1<<18)];10 LL cnt;11 12 inline void solve(int a,int b,int c,int d){13     int L=(a+c),R=(b+d);14     if(1LL*L*L+1LL*R*R>inf) return;15     if((R-L)%2) num[((max(2*R*L,R*R-L*L))%(1<<17))]++;16     solve(a,b,L,R); solve(L,R,c,d);17 }18 19 int main(){20     solve(0,1,1,1);21     LL t;22     scanf("%lld",&t);23     while(t--){24         LL ans=0;25         scanf("%d",&n);26         for(int i=0;i<(1<
      

区间dp，先处理出连续相同的块。

1.普通合并。

2.两侧相同的情况，合并两侧。

3.两侧和中间合并，且需要保证两侧和不超过3个并且中间的个数只能是1。

1 #include 
      
        2 using namespace std; 3  4 const int inf=0x3f3f3f3f; 5  6 int n; 7 char s[205]; 8  9 int tot;10 int a[205];11 int num[205];12 int dp[205][205];13 14 int main(){15     int t;16     scanf("%d",&t);17     int T=t;18     while(t--){19         tot=0;20         memset(num,0,sizeof(num));21         memset(dp,inf,sizeof(dp));22         scanf("%s",s+1);23         n=strlen(s+1);24         int cnt=1;25         for(int i=2;i<=n;i++){26             if(s[i]!=s[i-1]){27                 cnt%=3;28                 if(cnt==0) continue;29                 tot++;30                 a[tot]=s[i-1]-'0';31                 num[tot]=cnt;32                 cnt=1;33             }34             else cnt++;35             if(i==n){36                 if(cnt>=3) continue;37                 tot++;38                 a[tot]=s[i]-'0';39                 num[tot]=cnt;40             }41         }42         for(int i=1;i<=tot;i++){43             if(num[i]==1) dp[i][i]=2;44             else dp[i][i]=1;45         }46         for(int len=2;len<=tot;len++){47             for(int i=1;i<=tot-len+1;i++){48                 int j=i+len-1;49                 for(int k=i;k
      

直接模拟

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #include 
         
           5 #include 
          
         
        
       
      

边权*1000+1，结果为最大流对1000取模。

1 #include 
      
        2 using namespace std; 3 const int inf=0x3f3f3f3f; 4 const int MAXN=205; 5 int level[MAXN]; 6 int iter[MAXN]; 7 int head[MAXN],tot; 8 struct edge{ 9     int to,cap,Next;10 } e[2005];11 void init(){12     memset(head,-1,sizeof(head));13     tot=0;14 }15 void add(int from,int to,int cap){16     e[tot].Next=head[from];17     e[tot].to=to;18     e[tot].cap=cap;19     head[from]=tot;20     tot++;21 }22 void addedge(int from,int to,int cap){23     add(from,to,cap);24     add(to,from,0);25 }26 void bfs(int s){27     memset(level,-1,sizeof(level));28     queue
       
         q;29     level[s]=0;30     q.push(s);31     while(!q.empty()){32         int v=q.front(); q.pop();33         for(int i=head[v];~i;i=e[i].Next){34             edge &ed=e[i];35             if(ed.cap>0&&level[ed.to]<0){36                 level[ed.to]=level[v]+1;37                 q.push(ed.to);38             }39         }40     }41 }42 int dfs(int v,int t,int f){43     if(v==t) return f;44     for(int &i=iter[v];~i;i=e[i].Next){45         edge &ed=e[i];46         if(ed.cap>0&&level[v]
        
         0){49                 ed.cap-=d;50                 e[i^1].cap+=d;51                 return d;52             }53         }54     }55     return 0;56 }57 int max_flow(int s,int t){58     int flow=0;59     while(1){60         bfs(s);61         if(level[t]<0) return flow;62         memcpy(iter,head,sizeof(iter));63         int f;64         while((f=dfs(s,t,inf))>0){65             flow+=f;66         }67     }68 }69 70 int n,m;71 72 int main(){73     int t;74     scanf("%d",&t);75     while(t--){76         init();77         int s,t;78         scanf("%d%d",&n,&m);79         scanf("%d%d",&s,&t);80         for(int i=1;i<=m;i++){81             int u,v,w;82             scanf("%d%d%d",&u,&v,&w);83             addedge(u-1,v-1,w*1000+1);84         }85         int ans=max_flow(s-1,t-1);86         printf("%d\n",ans%1000);87     }88 89     return 0;90 }
        
       
      

链表维护当前剩余的点，队列维护可能被炸掉的点。

1 #include 
      
        2 using namespace std; 3  4 const int MAXN=1e5+5; 5  6 int n; 7 int a[MAXN]; 8 int in[MAXN]; 9 int vis[MAXN];10 int pre[MAXN];11 int Next[MAXN];12 13 void solve(int x){14     pre[Next[x]]=pre[x];15     Next[pre[x]]=Next[x];16     vis[x]=1;17 }18 19 int main(){20     int t;21     scanf("%d",&t);22     while(t--){23         queue
       
         q;24         scanf("%d",&n);25         for(int i=1;i<=n;i++){26             scanf("%d",&a[i]);27             Next[i]=i+1;28             pre[i]=i-1;29             vis[i]=0;30             in[i]=1;31             q.push(n+1-i);32         }33         while(!q.empty()){34             int u=q.front();35             q.pop(); in[u]=0;36             if(vis[u]) continue;37             int pos=u;38             if(pre[pos]>=1&&a[pos]
        
         =1&&a[pos]
         
          =1) solve(pos);48             }49         }50         int num=0;51         for(int i=1;i<=n;i++)52             if(!vis[i]) num++;53         printf("%d\n",num);54         for(int i=1;i<=n;i++)55             if(!vis[i]) printf("%d ",a[i]);56         printf("\n");57     }58 59     return 0;60 }
         
        
       
      

立方差公式为(a-b)(a^2+ab+b^2)，所以a,b需要相邻，预处理出所有的值，然后直接查找即可。

1 #include 
      
        2 using namespace std; 3 typedef long long LL; 4 vector
       
         v; 5 int main(){ 6     int t; 7     cin>>t; 8     for(LL i=1;i<=577350;i++){ 9         LL a=i,b=i+1;10         v.push_back(a*a+a*b+b*b);11     }12     sort(v.begin(),v.end());13     while(t--){14         LL x;15         cin>>x;16         LL id=lower_bound(v.begin(),v.end(),x)-v.begin();17         if(v[id]==x) cout<<"YES"<