这次div3比上次多一道， 也加了半小时， 说区分不出1600以上的水平。(我也不清楚）。

题意：给你一个数组，删除这个数组中相同的元素， 并且保留右边的元素。

代码：

1 #include
      
        2 using namespace std; 3 #define Fopen freopen("_in.txt","r",stdin); freopen("_out.txt","w",stdout); 4 #define LL long long 5 #define ULL unsigned LL 6 #define fi first 7 #define se second 8 #define pb push_back 9 #define lson l,m,rt<<110 #define rson m+1,r,rt<<1|111 #define max3(a,b,c) max(a,max(b,c))12 #define min3(a,b,c) min(a,min(b,c))13 typedef pair
       
         pll;14 const int INF = 0x3f3f3f3f;15 const LL mod = 1e9+7;16 const int N = 1e5+10;17 int vis[N];18 int a[N];19 int main(){20     ///Fopen;21     int n;22     int t = 0;23     scanf("%d", &n);24     for(int i = 1; i <= n; i++){25         scanf("%d", &a[i]);26         if(vis[a[i]] == 0) t++;27         vis[a[i]] = i;28     }29     printf("%d\n", t);30     for(int i = 1; i <= n; i++){31         if(vis[a[i]] == i){32             printf("%d ", a[i]);33         }34     }35     return 0;36 }
       
      

题意：不能有3个或以上的x连续出现，求删除几个x之后，不会有3个连续的x出现。

代码：

1 #include
      
        2 using namespace std; 3 #define Fopen freopen("_in.txt","r",stdin); freopen("_out.txt","w",stdout); 4 #define LL long long 5 #define ULL unsigned LL 6 #define fi first 7 #define se second 8 #define pb push_back 9 #define lson l,m,rt<<110 #define rson m+1,r,rt<<1|111 #define max3(a,b,c) max(a,max(b,c))12 #define min3(a,b,c) min(a,min(b,c))13 typedef pair
       
         pll;14 const int INF = 0x3f3f3f3f;15 const LL mod = 1e9+7;16 const int N = 1e5+10;17 char str[N];18 int main(){19     ///Fopen;20     int n;21     scanf("%d", &n);22     scanf("%s", str);23     str[n] = '.';24     int cnt = 0;25     int ans = 0;26     for(int i = 0; i <= n; i++){27         if(str[i] == 'x') cnt++;28         else {29             if(cnt >= 3) ans += cnt - 2;30             cnt = 0;31         }32     }33     printf("%d", ans);34     return 0;35 }
       
      

题意：这里有n个宿舍（楼），每个宿舍有a[i]个人，现在有m封信要寄过来，没有名字， 只有从第一个宿舍开始计数的第a[i]个人的信息， 求每封信对应的宿舍和第几个人。

题解：前缀和， 然后lowbound查找一下编号为b[i]的人， 转化信息一下就好了。

代码：

1 #include
      
        2 using namespace std; 3 #define Fopen freopen("_in.txt","r",stdin); freopen("_out.txt","w",stdout); 4 #define LL long long 5 #define ULL unsigned LL 6 #define fi first 7 #define se second 8 #define pb push_back 9 #define lson l,m,rt<<110 #define rson m+1,r,rt<<1|111 #define max3(a,b,c) max(a,max(b,c))12 #define min3(a,b,c) min(a,min(b,c))13 typedef pair
       
         pll;14 const int INF = 0x3f3f3f3f;15 const LL mod = 1e9+7;16 const int N = 2e5+10;17 int n, m;18 LL a[N];19 LL sum[N];20 int main(){21     ///Fopen;22     scanf("%d%d",  &n, &m);23     for(int i = 1; i <= n; i++){24         scanf("%I64d", &a[i]);25         sum[i] = sum[i-1] + a[i];26     }27     while(m--){28         LL tmp;29         scanf("%I64d", &tmp);30         int pos = lower_bound(sum+1,sum+1+n,tmp) - sum;31         printf("%d %I64d\n",pos, tmp - sum[pos-1]);32     }33     return 0;34 }
       
      

题意：给你一个数列， 可以将这将这个数列的任意一个元素加一，减一或者不改变， 求形成等差数列之后改变元素的次数最小， 如果没有办法形成等差数列， 就输出-1。

题解：看着很复杂， 但是如果第1个元素和第2个元素定下来了之后， 那么后面的元素都定下来了， 所以暴力枚举9种情况， 然后check一遍， 找到答案。

题解：

1 #include
      
        2 using namespace std; 3 #define Fopen freopen("_in.txt","r",stdin); freopen("_out.txt","w",stdout); 4 #define LL long long 5 #define ULL unsigned LL 6 #define fi first 7 #define se second 8 #define pb push_back 9 #define lson l,m,rt<<110 #define rson m+1,r,rt<<1|111 #define max3(a,b,c) max(a,max(b,c))12 #define min3(a,b,c) min(a,min(b,c))13 typedef pair
       
         pll;14 const int INF = 0x3f3f3f3f;15 const LL mod = 1e9+7;16 const int N = 1e5+10;17 int a[N];18 int b[N]; int n;19 int ans = INF;20 int check(int u){21     int cnt = 0;22     for(int i = 3; i <= n; i++){23         b[i] = b[i-1] + u;24         if(abs(a[i]-b[i]) > 1) return -1;25         if(abs(a[i]-b[i]) == 1) cnt++;26     }27     return cnt;28 }29 int d1[3]={
    1,0,-1};30 int d2[3]={
    1,0,-1};31 int main(){32     ///Fopen;33 34     scanf("%d", &n);35     for(int i = 1; i <= n; i++)36         scanf("%d", &a[i]);37     if(n == 1 || n == 2){38         printf("0");39         return 0;40     }41     for(int i = 0; i < 3; i++)42         for(int j = 0; j < 3; j++){43             b[1] = a[1] + d1[i];44             b[2] = a[2] + d2[j];45             int tmp = check(b[2]-b[1]);46             if(tmp != -1){47                 ans = min(ans, tmp+(i!=1)+(j!=1));48             }49     }50     if(ans == INF) printf("-1");51     else printf("%d", ans);52     return 0;53 }
       
      

题意：这里有一辆bus， 然后有n个站， 最多容纳m个人，每一个站都会有人上车下车，求始发点人数可能的情况数， 如果没办法就矛盾就输出0。

题解：记录下这辆车在车上最多多少人， 最少的时候多少人。 然后 通过最多人数 算出始发点 最多能有多少人， 通过最少的人数算出始发点最少多少人。 然后就得出答案了。

代码：

1 #include
      
        2 using namespace std; 3 #define Fopen freopen("_in.txt","r",stdin); freopen("_out.txt","w",stdout); 4 #define LL long long 5 #define ULL unsigned LL 6 #define fi first 7 #define se second 8 #define pb push_back 9 #define lson l,m,rt<<110 #define rson m+1,r,rt<<1|111 #define max3(a,b,c) max(a,max(b,c))12 #define min3(a,b,c) min(a,min(b,c))13 typedef pair
       
         pll;14 const int INF = 0x3f3f3f3f;15 const LL mod = 1e9+7;16 const int N = 1e5+10;17 int n, m;18 int main(){19     ///Fopen;20     scanf("%d%d", &n, &m);21     int l = 0, r = 0;22     int tmp = 0, t;23     while(n--){24         scanf("%d", &t);25         tmp += t;26         r = min(r, tmp);27         l = max(l, tmp);28     }29     int maxn = m - l;30     int minn = -r;31     int ans = maxn-minn+1;32     if(ans <= 0) ans = 0;33     printf("%d\n", ans);34     return 0;35 }
       
      

题意：有n个人， 每一个人有一个能力值， 然后求这个能力值高的人能当能力值低的人的导师，然后又m对人在吵架， 如果2个人吵架， 他们2个人就不能组成导师关系， 现在求每个人可以当多少个人的导师数目。

题解：map记录一下能力值， 然后 在用另一个map 对第一个map求前缀和， 然后映射出每个人可以当多少个人的导师数目， 然后对于吵架的人， 2方谁能力值高谁的数目就-1， 就可以得到答案了。

代码：

1 #include
      
        2 using namespace std; 3 #define Fopen freopen("_in.txt","r",stdin); freopen("_out.txt","w",stdout); 4 #define LL long long 5 #define ULL unsigned LL 6 #define fi first 7 #define se second 8 #define pb push_back 9 #define lson l,m,rt<<110 #define rson m+1,r,rt<<1|111 #define max3(a,b,c) max(a,max(b,c))12 #define min3(a,b,c) min(a,min(b,c))13 typedef pair
       
         pll;14 const int INF = 0x3f3f3f3f;15 const LL mod = 1e9+7;16 const int N = 2e5+10;17 int n, k;18 int a[N];19 int cnt[N];20 map
        
          mp;21 map
         
           mmp;22 int main(){23     ///Fopen;24     scanf("%d%d", &n, &k);25     for(int i = 1; i <= n; i++){26         scanf("%d", &a[i]);27         mp[a[i]]++;28     }29     int tmp = 0;30     map
          
           ::iterator it = mp.begin();31     while(it!=mp.end()){32         mmp[it->fi] = tmp;33         tmp += it->second;34         it++;35     }36     for(int i = 1; i <= n; i++){37         cnt[i] = mmp[a[i]];38     }39     int u, v;40     while(k--){41         scanf("%d%d", &u, &v);42         if(a[u] > a[v])cnt[u]--;43         else if(a[u] < a[v]) cnt[v]--;44     }45     for(int i = 1; i <= n; i++){46         printf("%d%c",cnt[i]," \n"[i==n]);47     }48     return 0;49 }
          
         
        
       
      

题意： Petyas有m门考试， 每一门考试有个s，d， c, 他只能在s,d-1之间复习这门科目并且要复习c天， 然后第d天要考试， Petays一天只能干一件事情， 求怎么样安排Petyas的时间使得Petya能通过所有考试的n天日程安排， 如果不行输出-1。

题解：贪心， 先安排考试时间早的， 如果有一门考试安排不下了， 就输出-1.

代码：

1 #include
      
        2 using namespace std; 3 #define Fopen freopen("_in.txt","r",stdin); freopen("_out.txt","w",stdout); 4 #define LL long long 5 #define ULL unsigned LL 6 #define fi first 7 #define se second 8 #define pb push_back 9 #define lson l,m,rt<<110 #define rson m+1,r,rt<<1|111 #define max3(a,b,c) max(a,max(b,c))12 #define min3(a,b,c) min(a,min(b,c))13 typedef pair
       
         pll;14 const int INF = 0x3f3f3f3f;15 const LL mod = 1e9+7;16 const int N = 1e3+10;17 int n, m;18 struct Node{19     int s, d, c;20     int id;21 22 }A[N];23 int vis[N];24 bool cmp(Node x, Node y){25     return x.d < y.d;26 }27 int main(){28     ///Fopen;29     scanf("%d%d", &n, &m);30     for(int i = 1; i <= m; i++){31         scanf("%d%d%d", &A[i].s, &A[i].d, &A[i].c);32         vis[A[i].d] = m+1;33         A[i].id = i;34     }35     sort(A+1, A+1+m, cmp);36     for(int i = 1; i <= m; i++){37         int cnt = 0;38         for(int j = A[i].s; j < A[i].d; j++){39             if(!vis[j]){40                 cnt++;41                 vis[j] = A[i].id;42                 if(cnt == A[i].c) break;43             }44         }45         if(cnt != A[i].c) {printf("-1"); return 0;}46     }47     for(int i = 1; i <= n; i++)48         printf("%d%c", vis[i], " \n"[i==n]);49     return 0;50 }