I 完美主义者dp,最长子序列的衍生。可参考经典题拦截导弹，那个是最长递增子序列。 代码： #include <bits/stdc++.h> using namespace std; int inc1[200],inc2[200],a[200]; int main(){ int n; while(scanf("%d",&n)!=EOF){ int ans=0,i,j; for(i = 0; i < n; i++)scanf("%d",&a[i]); //inc1[i]是存储以i为最高点时左边的递增...

H 修建道路最小生成树，模板题。所有城市两两可达，最少边数为n-1，然后再保留一下加入边的最大权值就行。 代码： #include<bits/stdc++.h> using namespace std; const int N=10010; struct node{ int u,v,c; }a[N]; int n,m,ans,fa[N]; bool cmp(node x,node y){return x.c<y.c;}//所有边按权值大到小排序 int find(int x){//并查集查找 return fa[x]==x?x:fa[x]=find(fa[x]...

G 相似每两个偶数和奇数都能凑一组，所以奇数和偶数的数量为偶数时一定能配对。并且最多多出一个奇数和一个偶数不能配对。只要连续出现的组数超过一组，就可以控制多出来的那组奇数和偶数为连续组。 代码： #include<bits/stdc++.h> using namespace std; int a[60],b[2];//数组b用来存奇数和偶数的数量 int main(){ int t; cin>>t; while(t--){ int n; scanf("%d",&n); memset(b,0,...

F 考试成绩拓扑排序，模板题。 代码： #include<stdio.h> #include<cstring> const int Max=505; int N,M; int used[Max];//如果这个点当过起点，就删掉 int Map[Max][Max];//保存关系，也就是边 int in_degree[Max];//保存每个点的入度 int ans[Max]; void toposort() { int cn=0;//一共要进行N个数的输出，所以我们需要 while(cn<N) { int i,j; ...

E 宝藏男孩简单dp，也就是说，还是找规律。long long必不可少。最后存放宝藏的位置一定是最中间的位置。画个图就知道规律了。 代码： #include<bits/stdc++.h> using namespace std; typedef long long ll; ll dp[500010]; void f(){ dp[1]=0; for(ll i=3;i<500010;i+=2) dp[i]=dp[i-2]+4*(i-1)*(i/2);//其中4*(n-1)为最外围的格子数。n/2为最外围格子到达最中间格子需要的步数。 } int m...

D 简单粗暴串签到，字符串查找子串，注意不可重复。 用到字符串查找子串函数：find(string,int)第一个参数为待查找子串，第二个参数为开始查找位置。找到返回该子串首字母下标，未找到返回string::npos。 代码： #include<bits/stdc++.h> using namespace std; int main(){ string s,c; while(cin>>s>>c){ if(s=="#")break; int ans=0; int l=c.size(); ...

C 花生米简单dp，或者说，找规律。dp[70]的时候有2073693258389777176，所以dp要用long long存，不然会炸。 先算几组，dp[1]=1,dp[2]=2,dp[3]=4,dp[4]=7,dp[5]=13......得公式为dp[i]=dp[i-1]+dp[i-2]+dp[i-3]; 还是算不出这个公式的话，我可以再详细帮你们算一下。dp[1]=1 [1]dp[2]=2 [11,2]dp[3]=4 [111,12,21,3]dp[4]=7[1111,112,121,13]，开头为1的时候为dp[3]=4[211,22]，开头为2的时候为dp[2]=2[31]，开头为...

B 打赌gcd啊，大部分人刚开始考虑到的状况都是gcd等于1或者gcd等于2的。把数据放大到20 30 60，就知道是求gcd了。 代码： # include<bits/stdc++.h> using namespace std; int gcd(int a,int b){ return b==0?a:gcd(b,a%b); } int main(){ int n,m; while(~scanf("%d%d",&n,&m)){ int k=gcd(n,m); int c1=n/k; in...

A 下棋博弈论。不管选哪个棋子作为矩形的右下角，棋盘左上角都包含在被选矩形中。若轮到你时，左上角为黑，你行动完，它变为白，对手行动完，它必会变成黑，即，你已经立于不败之地了。 结论：若左上角为黑，先手必胜；若左上角为白，后手必胜。 代码： #include<bits/stdc++.h> using namespace std; int main(){ int t; cin>>t; while(t--){ int n,m; cin>>n>>m;//棋盘大小 char ch; ...

#include<bits/stdc++.h> using namespace std; int c[1010],w[1010][8]; int main(){     int n,e;     while(~scanf("%d%d",&n,&e)){         memset(w,0,sizeof(w));         int flag=0;         for(int i=0;i<n;i++){             int m;             scanf("%d%d",&c[i],&...

D 最大字符集1和2特判，其余都为11,101,1001,10001,100001...... #include<bits/stdc++.h> using namespace std; int main(){ int n; while(cin>>n){ if(n==1){ cout<<1<<endl<<1<<endl;continue; } if(n==2){ cout<<2<<endl&...

F 日期小助手母亲节在8到14之间变动，父亲节在15到21之间变动，注意闰年对日期变动的影响，以及，2100年不是闰年，刚开始在2100卡死也是够了。 #include<bits/stdc++.h> using namespace std; int main(){ int t; cin>>t; while(t--){ int y,m,d; cin>>y>>m>>d; int mo=14-((y-2000)+(y-2000)/4)%7; int fa...

E 美味的序列边加边减就行，用long long存答案，顺便一提，全加起来再减应该不行，过不了 #include<bits/stdc++.h> using namespace std; typedef long long ll; bool cmp(int a,int b){return a>b;} int a[100010]; int main(){ int n; while(cin>>n){ for(int i=0;i<n;i++){ scanf("%d",&a[i]); } ...

C 最长非公共子序列如果两个字符串相等则是-1，否则为最长字符串的长度 #include<bits/stdc++.h> using namespace std; int main(){ string s1,s2; while(cin>>s1>>s2){ if(s1.size()!=s2.size()){ cout<<max(s1.size(),s2.size())<<endl;; } else if(s1!=s2){ cou...