1.分而治之题目链接
分而治之，各个击破是兵家常用的策略之一。在战争中，我们希望首先攻下敌方的部分城市，使其剩余的城市变成孤立无援，然后再分头各个击破。为此参谋部提供了若干打击方案。本题就请你编写程序，判断每个方案的可行性。
输入格式： 输入在第一行给出两个正整数 N 和 M（均不超过10 000），分别为敌方城市个数（于是默认城市从 1 到 N 编号）和连接两城市的通路条数。随后 M 行，每行给出一条通路所连接的两个城市的编号，其间以一个空格分隔。在城市信息之后给出参谋部的系列方案，即一个正整数 K （≤ 100）和随后的 K 行方案，每行按以下格式给出：
Np v[1] v[2] … v[Np] 其中 Np 是该方案中计划攻下的城市数量，后面的系列 v[i] 是计划攻下的城市编号。
输出格式： 对每一套方案，如果可行就输出YES，否则输出NO。
题意总结一下就是将给出的v[1] v[2] … v[Np]全部去除后剩余的城市是否互不连接。用一个邻接表可以很轻易的做出来。通过vector数组存储每个城市连接的其余城市。该城市被攻破后。将其连接其他城市道路数改为0再通过vector数组检索，将其连接的每个城市的道路数都-1.若最后所有城市的道路都小于等于0即为可行。 AC代码：
#include<iostream> #include<vector> #include<cstring> using namespace std; vector <vector<int > > xd; int nn[10005]; int n,m; void print(){ for(int i = 1; i <= n; i++){ if(nn[i] > 0){cout << "NO" << endl;return;} } cout << "YES" << endl; } int main(){ int num[10005]={0}; memset(num,0,sizeof(num)); cin>>n>>m; xd.resize(n + 1); for(int i=0;i<m;i++){ int a,b; cin>>a>>b; xd[a].push_back(b); xd[b].push_back(a); num[a]++; num[b]++; } int k; cin>>k; while(k--){ int np; cin>>np; for(int i=0;i<n;i++){ nn[i]=num[i]; } while(np--){ int v; cin>>v; nn[v]=0; for(int i=0;i<xd[v].size();i++){ nn[xd[v][i]]--; } } int f=0; for(int i = 1; i <= n; i++){ if(nn[i] > 0){cout << "NO" << endl;f=1;break;} } if(f)continue; cout << "YES" << endl; } }2.重拍链表 给定一个单链表 L1 →L2 →⋯→Ln−1 →Ln ，请编写程序将链表重新排列为 Ln →L1 →Ln−1 →L2 →⋯。例如：给定L为1→2→3→4→5→6，则输出应该为6→1→5→2→4→3。
输入格式： 每个输入包含1个测试用例。每个测试用例第1行给出第1个结点的地址和结点总个数，即正整数N (≤10 5 )。结点的地址是5位非负整数，NULL地址用−1表示。
接下来有N行，每行格式为：
Address Data Next 其中Address是结点地址；Data是该结点保存的数据，为不超过10 5 的正整数；Next是下一结点的地址。题目保证给出的链表上至少有两个结点。
输出格式： 对每个测试用例，顺序输出重排后的结果链表，其上每个结点占一行，格式与输入相同。
当时做题的时候没有考虑到有多余节点的情况。按照题意将过程模拟出来即可。
#include<iostream> #include<cstring> #include<cstdio> using namespace std; struct lb{ int da,ne; }p[100005]; int main(){ int be,n; cin>>be>>n; for(int i=0;i<n;i++){ int a,b,c; cin>>a>>b>>c; p[a].da=b; p[a].ne=c; } int aa[100005]; int c=0; while(be!=-1){ aa[c]=be; be=p[be].ne; c++; } int l=c; c=0; int res[100005]; int i=0,j=l-1; while(i<=j){ if(i==j){ res[c]=aa[i]; } else{ res[c++]=aa[j--]; res[c++]=aa[i++]; } } for(i=0;i<l-1;i++){ printf("%05d %d %05d\n",res[i],p[res[i]].da,res[i+1]); } printf("%05d %d -1\n",res[l-1],p[res[l-1]].da); }