23.4.15 NOIP2010提高游记

第一次做提高，之前做的都是普及，还是感觉挺难的，心态有点裂开。

1．机器翻译

这题首先一看就是一道模拟题目，要注意的是字典的内存问题，在超内存以后要减1，直接上代码 :-) ，时间复杂度O(n)

 1 #include<bits/stdc++.h>
 2 #pragma GCC opzimize(3)
 3 using namespace std;
 4 inline long long read(){
 5     long long ans=0,f=1;
 6     char ch=getchar();
 7     if(ch=='-'){
 8         f=-1;
 9     }
10     while(!isdigit(ch)){
11         ch=getchar();
12     }
13     while(isdigit(ch)){
14         ans=((ans<<1)+(ans<<3)+(ch^48));
15         ch=getchar(); 
16     }
17     return ans*f;
18 }
19 int main(){
20     queue<int> q;
21     int m=read(),n=read(),ans;
22     bool inq[1010];
23     for(int i=1;i<=n;i++){
24         int x=read();
25         if(inq[x])continue;
26         else{
27             if(q.size()>=m){
28                 inq[q.front()]=false;
29                 q.pop();
30             }
31             q.push(x);
32             inq[x]=true;
33             ans++;
34         }
35     }
36     cout<<ans;
37     return 0;
38 }

2．乌龟棋

一拿到这题就想到是一道DP题，首先推状态转移方程，F[i][j][k][l]表示走后分数的状况，因为有4个维度可以推出不同的情况，则有

 1 if(i){
 2 f[i][j][k][l]=max(f[i][j][k][l],f[i-1][j][k][l]+a[s]);
 3 }
 4 if(j){
 5 f[i][j][k][l]=max(f[i][j][k][l],f[i][j-1][k][l]+a[s]);
 6 }
 7 if(k){
 8 f[i][j][k][l]=max(f[i][j][k][l],f[i][j][k-1][l]+a[s]);
 9 }
10 if(l){
11 f[i][j][k][l]=max(f[i][j][k][l],f[i][j][k][l-1]+a[s]);
12 }

综合一下4重循环，代码就出来了

 1 f[0][0][0][0]=a[1];//记得把起始点加进去
 2 for(int i=0;i<=b[1];i++){
 3     for(int j=0;j<=b[2];j++){
 4         for(int k=0;k<=b[3];k++){
 5             for(int l=0;l<=b[4];l++){
 6                 s=i+j*2+k*3+l*4+1;
 7                 if(i){
 8                     f[i][j][k][l]=max(f[i][j][k][l],f[i-1][j][k][l]+a[s]);
 9                 }
10                 if(j){
11                     f[i][j][k][l]=max(f[i][j][k][l],f[i][j-1][k][l]+a[s]);
12                 }
13                 if(k){
14                     f[i][j][k][l]=max(f[i][j][k][l],f[i][j][k-1][l]+a[s]);
15                 }
16                 if(l){
17                     f[i][j][k][l]=max(f[i][j][k][l],f[i][j][k][l-1]+a[s]);
18                 }
19                 f[i][j][k][l]+=a[s];
20             }
21         }
22     }
23 }

下面是完整版的代码，时间复杂度最大O(40^4)

 1 #include<bits/stdc++.h>
 2 #define N 360
 3 #define M 5
 4 using namespace std; 
 5 int a[N],b[M],f[41][41][41][41];
 6 int main(){
 7     int n,m,s=0;
 8     cin>>n>>m;
 9     for(int i=1;i<=n;i++){
10         cin>>a[i];
11     } 
12     for(int i=1;i<=m;i++){
13         int pp;
14         cin>>pp;
15         b[pp]++;
16     }
17     f[0][0][0][0]=a[1];
18     for(int i=0;i<=b[1];i++){
19         for(int j=0;j<=b[2];j++){
20             for(int k=0;k<=b[3];k++){
21                 for(int l=0;l<=b[4];l++){
22                     s=i+j*2+k*3+l*4+1;
23                     if(i){
24                         f[i][j][k][l]=max(f[i][j][k][l],f[i-1][j][k][l]+a[s]);
25                     }
26                     if(j){
27                         f[i][j][k][l]=max(f[i][j][k][l],f[i][j-1][k][l]+a[s]);
28                     }
29                     if(k){
30                         f[i][j][k][l]=max(f[i][j][k][l],f[i][j][k-1][l]+a[s]);
31                     }
32                     if(l){
33                         f[i][j][k][l]=max(f[i][j][k][l],f[i][j][k][l-1]+a[s]);
34                     }
35                     f[i][j][k][l]+=a[s];
36                 }
37             }
38         }
39     }
40     cout<<f[b[1]][b[2]][b[3]][b[4]]/2;
41     return 0;
42 }

到这儿，接下来就是考场上没做的了qwq

3．关押罪犯

读题可以发现，我们需要通过哪些人应该在不同的监狱来倒推出哪些人应该在相同的监狱，所以想到用并查集来维护。

本题需要用到种类并查集来维护A监狱和B监狱，这题有贪心的雏形，在对怨气值排序后，我们可以让怨气值最大的一对犯人分别在两个监狱，如果A为B的敌人，那就去另一个监狱，反之就在一个监狱。当A与B、C皆为敌人时，此时就为最小影响力了，因为排序保证了单调递减性。

Question：为什么本题不用并查集，而用种类并查集呢？

Answer：一般的并查集，维护的是具有连通性、传递性的关系，例如亲戚的亲戚是亲戚。但是，有时候，我们要维护另一种关系：敌人的敌人是朋友。种类并查集就是为了解决这个问题而诞生的。所以我们要用种类并查集来解决这个问题。

所以本题内我们还要注意敌人的敌人是朋友这一关系，所以当A和B为敌人，B和C为敌人时，A与C在没有说明是敌人的情况下是朋友关系，所以这时我们能把C放在A所在的监狱去。

我们就可以得到一种类似于跳板的东西，例如 A->B->C->D中(“->”在这里表示仇恨关系)，A可以和C、D在一起，B可以和D在一起、C可以和A在一起，D可以和B在一起。所以我们就可以得到一种安全的方案，即为a[A,C] and b[B,D]。就可以发现，只要在关系中成线性结构，便可以得到一个安全关系。但是如果出现了环，则有冲突事件的必然发生，所以我们得到了一种新作法，判断是否有环。

注意！没有要输出0！

Code:并查集

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<iomanip>
 4 #include<algorithm>
 5 #define rg register int//卡常
 6 
 7 using namespace std;
 8 
 9 struct su{
10     int f,t,v;
11 }a[100010];
12 
13 int n,m,l,r,mid,f;
14 int s[20001<<1]; //不要单独开两数组！
15 
16 inline int qr(){  char ch; //快读
17     while((ch=getchar())<'0'||ch>'9');
18     int res=ch^48;
19     while((ch=getchar())>='0'&&ch<='9')
20         res=res*10+(ch^48);
21     return res;
22 }
23 
24 inline bool cmp(su x,su y){
25     return x.v>y.v; //从大到小排序
26 }
27 
28 inline int get(int x){
29     if(x==s[x])return x;
30     return s[x]=get(s[x]);//路径压缩
31 }
32 
33 int main(){
34     n=qr(),m=qr();
35     for(rg i=1;i<=m;++i)
36         a[i].f=qr(),a[i].t=qr(),a[i].v=qr();
37     sort(a+1,a+m+1,cmp); //贪心
38     for(rg i=1;i<=n;++i)
39         s[i]=i,s[i+n]=i+n; //初始化不能忘！！！
40     for(rg i=1;i<=m;++i){
41         rg x=a[i].f,y=a[i].t;
42         if(get(x)==get(y)||get(x+n)==get(y+n)){
43             f=a[i].v;break;//不能在同一监狱的仇人撞上了
44         }
45         s[s[x+n]]=s[y];
46         s[s[x]]=s[y+n];//维护两罪犯在不同监狱的关系
47     }printf("%d\n",f);
48     return 0;
49 }