CodeForces Round#480 div3 第2场

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

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

代码：

 #include<bits/stdc++.h>

 using namespace std;

 #define Fopen freopen("_in.txt","r",stdin); freopen("_out.txt","w",stdout);

 #define LL long long

 #define ULL unsigned LL

 #define fi first

 #define se second

 #define pb push_back

 #define lson l,m,rt<<1

 #define rson m+1,r,rt<<1|1

 #define max3(a,b,c) max(a,max(b,c))

 #define min3(a,b,c) min(a,min(b,c))

 typedef pair<int,int> pll;

 const int INF = 0x3f3f3f3f;

 const LL mod = 1e9+;

 const int N = 1e5+;

 int vis[N];

 int a[N];

 int main(){

     ///Fopen;

     int n;

     int t = ;

     scanf("%d", &n);

     for(int i = ; i <= n; i++){

         scanf("%d", &a[i]);

         if(vis[a[i]] == ) t++;

         vis[a[i]] = i;

     }

     printf("%d\n", t);

     for(int i = ; i <= n; i++){

         if(vis[a[i]] == i){

             printf("%d ", a[i]);

         }

     }

     return ;

 }

B. File Name

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

代码：

 #include<bits/stdc++.h>

 using namespace std;

 #define Fopen freopen("_in.txt","r",stdin); freopen("_out.txt","w",stdout);

 #define LL long long

 #define ULL unsigned LL

 #define fi first

 #define se second

 #define pb push_back

 #define lson l,m,rt<<1

 #define rson m+1,r,rt<<1|1

 #define max3(a,b,c) max(a,max(b,c))

 #define min3(a,b,c) min(a,min(b,c))

 typedef pair<int,int> pll;

 const int INF = 0x3f3f3f3f;

 const LL mod = 1e9+;

 const int N = 1e5+;

 char str[N];

 int main(){

     ///Fopen;

     int n;

     scanf("%d", &n);

     scanf("%s", str);

     str[n] = '.';

     int cnt = ;

     int ans = ;

     for(int i = ; i <= n; i++){

         if(str[i] == 'x') cnt++;

         else {

             if(cnt >= ) ans += cnt - ;

             cnt = ;

         }

     }

     printf("%d", ans);

     return ;

 }

C. Letters

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

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

代码：

 #include<bits/stdc++.h>

 using namespace std;

 #define Fopen freopen("_in.txt","r",stdin); freopen("_out.txt","w",stdout);

 #define LL long long

 #define ULL unsigned LL

 #define fi first

 #define se second

 #define pb push_back

 #define lson l,m,rt<<1

 #define rson m+1,r,rt<<1|1

 #define max3(a,b,c) max(a,max(b,c))

 #define min3(a,b,c) min(a,min(b,c))

 typedef pair<int,int> pll;

 const int INF = 0x3f3f3f3f;

 const LL mod = 1e9+;

 const int N = 2e5+;

 int n, m;

 LL a[N];

 LL sum[N];

 int main(){

     ///Fopen;

     scanf("%d%d",  &n, &m);

     for(int i = ; i <= n; i++){

         scanf("%I64d", &a[i]);

         sum[i] = sum[i-] + a[i];

     }

     while(m--){

         LL tmp;

         scanf("%I64d", &tmp);

         int pos = lower_bound(sum+,sum++n,tmp) - sum;

         printf("%d %I64d\n",pos, tmp - sum[pos-]);

     }

     return ;

 }

D. Almost Arithmetic Progression

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

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

题解：

 #include<bits/stdc++.h>

 using namespace std;

 #define Fopen freopen("_in.txt","r",stdin); freopen("_out.txt","w",stdout);

 #define LL long long

 #define ULL unsigned LL

 #define fi first

 #define se second

 #define pb push_back

 #define lson l,m,rt<<1

 #define rson m+1,r,rt<<1|1

 #define max3(a,b,c) max(a,max(b,c))

 #define min3(a,b,c) min(a,min(b,c))

 typedef pair<int,int> pll;

 const int INF = 0x3f3f3f3f;

 const LL mod = 1e9+;

 const int N = 1e5+;

 int a[N];

 int b[N]; int n;

 int ans = INF;

 int check(int u){

     int cnt = ;

     for(int i = ; i <= n; i++){

         b[i] = b[i-] + u;

         if(abs(a[i]-b[i]) > ) return -;

         if(abs(a[i]-b[i]) == ) cnt++;

     }

     return cnt;

 }

 int d1[]={,,-};

 int d2[]={,,-};

 int main(){

     ///Fopen;

     scanf("%d", &n);

     for(int i = ; i <= n; i++)

         scanf("%d", &a[i]);

     if(n ==  || n == ){

         printf("");

         return ;

     }

     for(int i = ; i < ; i++)

         for(int j = ; j < ; j++){

             b[] = a[] + d1[i];

             b[] = a[] + d2[j];

             int tmp = check(b[]-b[]);

             if(tmp != -){

                 ans = min(ans, tmp+(i!=)+(j!=));

             }

     }

     if(ans == INF) printf("-1");

     else printf("%d", ans);

     return ;

 }

E. Bus Video System

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

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

代码：

 #include<bits/stdc++.h>

 using namespace std;

 #define Fopen freopen("_in.txt","r",stdin); freopen("_out.txt","w",stdout);

 #define LL long long

 #define ULL unsigned LL

 #define fi first

 #define se second

 #define pb push_back

 #define lson l,m,rt<<1

 #define rson m+1,r,rt<<1|1

 #define max3(a,b,c) max(a,max(b,c))

 #define min3(a,b,c) min(a,min(b,c))

 typedef pair<int,int> pll;

 const int INF = 0x3f3f3f3f;

 const LL mod = 1e9+;

 const int N = 1e5+;

 int n, m;

 int main(){

     ///Fopen;

     scanf("%d%d", &n, &m);

     int l = , r = ;

     int tmp = , t;

     while(n--){

         scanf("%d", &t);

         tmp += t;

         r = min(r, tmp);

         l = max(l, tmp);

     }

     int maxn = m - l;

     int minn = -r;

     int ans = maxn-minn+;

     if(ans <= ) ans = ;

     printf("%d\n", ans);

     return ;

 }

F. Mentors

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

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

代码：

 #include<bits/stdc++.h>

 using namespace std;

 #define Fopen freopen("_in.txt","r",stdin); freopen("_out.txt","w",stdout);

 #define LL long long

 #define ULL unsigned LL

 #define fi first

 #define se second

 #define pb push_back

 #define lson l,m,rt<<1

 #define rson m+1,r,rt<<1|1

 #define max3(a,b,c) max(a,max(b,c))

 #define min3(a,b,c) min(a,min(b,c))

 typedef pair<int,int> pll;

 const int INF = 0x3f3f3f3f;

 const LL mod = 1e9+;

 const int N = 2e5+;

 int n, k;

 int a[N];

 int cnt[N];

 map<int,int> mp;

 map<int,int> mmp;

 int main(){

     ///Fopen;

     scanf("%d%d", &n, &k);

     for(int i = ; i <= n; i++){

         scanf("%d", &a[i]);

         mp[a[i]]++;

     }

     int tmp = ;

     map<int,int>::iterator it = mp.begin();

     while(it!=mp.end()){

         mmp[it->fi] = tmp;

         tmp += it->second;

         it++;

     }

     for(int i = ; i <= n; i++){

         cnt[i] = mmp[a[i]];

     }

     int u, v;

     while(k--){

         scanf("%d%d", &u, &v);

         if(a[u] > a[v])cnt[u]--;

         else if(a[u] < a[v]) cnt[v]--;

     }

     for(int i = ; i <= n; i++){

         printf("%d%c",cnt[i]," \n"[i==n]);

     }

     return ;

 }

G. Petya's Exams

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

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

代码：

 #include<bits/stdc++.h>

 using namespace std;

 #define Fopen freopen("_in.txt","r",stdin); freopen("_out.txt","w",stdout);

 #define LL long long

 #define ULL unsigned LL

 #define fi first

 #define se second

 #define pb push_back

 #define lson l,m,rt<<1

 #define rson m+1,r,rt<<1|1

 #define max3(a,b,c) max(a,max(b,c))

 #define min3(a,b,c) min(a,min(b,c))

 typedef pair<int,int> pll;

 const int INF = 0x3f3f3f3f;

 const LL mod = 1e9+;

 const int N = 1e3+;

 int n, m;

 struct Node{

     int s, d, c;

     int id;

 }A[N];

 int vis[N];

 bool cmp(Node x, Node y){

     return x.d < y.d;

 }

 int main(){

     ///Fopen;

     scanf("%d%d", &n, &m);

     for(int i = ; i <= m; i++){

         scanf("%d%d%d", &A[i].s, &A[i].d, &A[i].c);

         vis[A[i].d] = m+;

         A[i].id = i;

     }

     sort(A+, A++m, cmp);

     for(int i = ; i <= m; i++){

         int cnt = ;

         for(int j = A[i].s; j < A[i].d; j++){

             if(!vis[j]){

                 cnt++;

                 vis[j] = A[i].id;

                 if(cnt == A[i].c) break;

             }

         }

         if(cnt != A[i].c) {printf("-1"); return ;}

     }

     for(int i = ; i <= n; i++)

         printf("%d%c", vis[i], " \n"[i==n]);

     return ;

 }

巴特西

CodeForces Round#480 div3 第2场

最新文章

热门文章