地址：codeforce第84轮（div3）

A：

题目的意思是：给定我们一堆包含两个字符的字符串，字符串a和字符串b只要a的后一个字母和b的前一个字母相等即可链接，现在给出最后链接好的字符串，问我们最少能用多少个形如a和b的字符串可以链接；

实际上就是问我们，用多少个包含两个字符的字符串可以构造出答案，可以直接把所有情况写出来，去重即可；

这里可以直接用set去重，你也可以用map，反正哈希表基本都可以

代码如下：

#include<iostream>
#include<set>
using namespace std;
set<string> a;
int main()
{int t;cin>>t;while(t--){a.clear();int n;string arr;cin>>n;cin>>arr;
//		cout<<arr<<endl;for(int i=1;i<arr.size();i++){string k="";k+=arr[i-1];k+=arr[i];
//			cout<<k<<endl;a.insert(k);}cout<<a.size()<<endl;}} 

B：

b题乍一看我们需要找到一个b数组的一个序列，使得a和b的差值能够小于k；

这里我们考虑暴力写法，如果暴力的话我们需要枚举所有情况，因为b的某个数分配给a的某个数之后可能造成a的另一个数得不到分配，这是可能存在的；比如a={3,7}，b={8,1}，k=5，第一次选择会把8分给3，但是接下来1不能分配给7，但是我们发现把1分给3，把8分给3是可以的；

所以这道题到这里的分析大家也就看出来了；

因为我们保证题目有解，所有我们把a排序之后，把b排序之后，如果bi+1能分配给ai，那么bi一定能分配给ai。前面情况一样，这样我们就得到了一种最优算法，虽然答案不唯一，但是这种情况很好写。

开个struct，一个变量存a的值，一个存位置，进行a和b的排序之后，再根据结构体位置信息把b按照顺序输出，我这里是开了一个数组再存了一次。

代码：

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
struct ST
{int k;int si;
}a[100010];
int ans[100010];
int b[100010];int cmp(ST a,ST b)
{return a.k<b.k;
}int main()
{int t,m;cin>>t;while(t--){int n;cin>>n>>m;for(int i=1;i<=n;i++){cin>>a[i].k;a[i].si=i;}for(int i=1;i<=n;i++){cin>>b[i];}sort(a+1,a+n+1,cmp);sort(b+1,b+n+1);for(int i=1;i<=n;i++){ans[a[i].si]=b[i];}for(int i=1;i<=n;i++) cout<<ans[i]<<' ';cout<<endl;}
}

C：

首先题目让我们构造出全奇数或者全偶数序列，这个时候我们就要考虑给我们的序列的分布情况，首先全是奇数和全是偶数肯定是有答案的，直接输出YES，这里我们思考有奇数和有偶数的情况，我们思考能否构造出偶数数列；

显而易见这是不可能的，因为奇数减奇数为偶数，你可以用大的奇数减小的奇数得到偶数，但是会剩下最后一个最小的奇数没法减去，所以可以思考构造奇数序列，这里我们发现奇数序列只需要用偶数减去最小的奇数就可以构造。所以不成立的情况就是，存在一个偶数小于最小的奇数。

直接进行遍历，存下奇数个数，偶数个数，奇数最小值，偶数最小值，当偶数最小值小于奇数最小值一定无解即可；

代码：

#include<iostream>using namespace std;int arr[200010];int main()
{int t;cin>>t;while(t--){int n,ji=0x3f3f3f3f,ou=0x3f3f3f3f,inj=0,ino=0;cin>>n;for(int i=1;i<=n;i++){int k;cin>>k;if(k%2) inj++,ji=min(k,ji);else ino++,ou=min(ou,k);}if(!inj||!ino) cout<<"YES"<<endl;else {if(ou<ji) cout<<"NO"<<endl;else cout<<"YES"<<endl;}}
}

D:

这道题目需要好好思考一下，题目告诉我们需要找到其中一个区间进行反转，再把前后交换得到答案，这里我们想，如何才能使字典序最大呢？

肯定是要先把最大的数字放在最前面，那么根据这个情况，我们能找到两种解决方案，一种是找到最大数字的前一个，让他变成r位置，遍历l位置，模拟reverse过程计算一个答案。还有一种情况就是选择最大值，这个时候只会在最大值在最后一个数的时候成立，因为如果最大数不在最后一个位置，你选择以后交换前后值得时候肯定有数字在最大值前面，所以这个不可以。

还有一种情况是最大值在最前面，因为我们进行选择的时候，反转的数组一定在最大值前面，所以当最大在第一个，你的数组是一定会把最大值调到后面的，这个时候我们就要考虑次最大值了。

我们可以选择次最大值，这样次最大值进行选择的时候还是会把最大值移位，并且在次最大值排最前面的选择里，一定可以达到最大；

写法就是模拟上述这个过程

代码：

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;int n,ma=0,si=0;
const int N=2010;
int pd[N],arr[N],b[N];
int ans[N];int rever(int l,int r)
{for(int i=l,j=r;i<j;i++,j--){swap(b[i],b[j]);}
}
int cun(int l,int r)
{int o=1;for(int i=r;i<=n;i++) pd[o++]=b[i];for(int i=l+1;i<=r-1;i++) pd[o++]=b[i];for(int i=1;i<=l;i++) pd[o++]=b[i];
}int pdsw()
{int flag=0;for(int i=1;i<=n;i++){if(pd[i]>ans[i]){flag=1;break;}else if(pd[i]<ans[i]){flag=0;break;}}if(flag){for(int i=1;i<=n;i++) ans[i]=pd[i];}
}int main()
{int t;cin>>t;while(t--){memset(ans,0,sizeof(ans));ma=0,si=0;cin>>n;for(int i=1;i<=n;i++){cin>>arr[i];if(arr[i]>ma) ma=arr[i],si=i;}if(si==1){for(int i=1;i<=n;i++){if(arr[i]==ma-1) {si=i;break;}}}for(int i=si-1;i>=1;i--) {
//			cout<<i<<' '<<si-1<<endl;for(int j=1;j<=n;j++) b[j]=arr[j];rever(i,si-1);//			for(int j=1;j<=n;j++) cout<<b[j]<<' ';
//			cout<<endl;cun(i-1,si);pdsw();}for(int i=si;i>=1;i--) {
//			cout<<i<<' '<<si<<endl;for(int j=1;j<=n;j++) b[j]=arr[j];rever(i,si);//			for(int j=1;j<=n;j++) cout<<b[j]<<' ';
//			cout<<endl;cun(i-1,si+1);pdsw();}for(int i=1;i<=n;i++) cout<<ans[i]<<' ';cout<<endl;}
}

E：

这道题目有很强的思维性。

我们首先考虑，每个点只知道他的一个邻居，不知道另一个邻居，这样我们需要查找到最大的和最小的围圈跳舞的人是多少。我们把这个点和他们的邻居连起来，我们会发现有些成环了，而有些没有成环却成边。

如果你多测几组样例很容易就能发现一个问题，一个点不可能和3个及以上点相连，因为那样会造成邻居错误，所以当某一条链成环，她肯定会绕回去。而其他情况也只会成一条竹子型的边，我们下边都简称边。

一个环是一种情况，所有边最小可以成一个环也可以没有，最大每一条边连一个环，边数就等于环数。

我们如何找成边和成环的情况呢？

首先可以用无向图来做，用无向图来存的话，成环说明这条边至少有两个出边，成边说明有一个点只有一条边，可以直接判断不是上一个节点的话，没有节点了，就是边，如果还有并且重复了就是环。

也可以直接从某一个点进入，把这条边或者环所有点存进去，左后判断，只要有一个点只有一条出边就是错误。。

这样我们无论根据上述那种方法都可以计算出来；

这里我使用的是第二种方法；

代码如下：

#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
#include<set>
#include<queue>
using namespace std;typedef long long LL;
const int N=200010;int main()
{int t;cin>>t;while(t--){int n;cin>>n;vector<set<int>> g(n);vector<int> a(n);vector<int> d(n);for(int i=0;i<n;i++){cin>>a[i];a[i]--;g[i].insert(a[i]);g[a[i]].insert(i);}for(int i=0;i<n;i++) d[i]=g[i].size(); int ba=0,cir=0;vector<int> vis(n);for(int i=0;i<n;i++){if(!vis[i]){queue<int> q;q.push(i);vis[i]=1;vector<int> ans = {i};while(!q.empty()){int u=q.front();q.pop();for(auto v:g[u]){if(!vis[v]){vis[v]=1;q.push(v);ans.push_back(v);}}}int bam=0;for(auto it:ans){if(d[it]==1){bam=1;break;}}if(bam) ba++;else cir++; }}cout<<cir+min(1,ba)<<' '<<cir+ba<<endl;}}