首页 > 代码库 > codeforces练习
codeforces练习
Description
DZY loves colors, and he enjoys painting.
On a colorful day, DZY gets a colorful ribbon, which consists of n units (they are numbered from 1 to n from left to right). The color of the i-th unit of the ribbon is i at first. It is colorful enough, but we still consider that the colorfulness of each unit is 0 at first.
DZY loves painting, we know. He takes up a paintbrush with color x and uses it to draw a line on the ribbon. In such a case some contiguous units are painted. Imagine that the color of unit i currently is y. When it is painted by this paintbrush, the color of the unit becomes x, and the colorfulness of the unit increases by |x - y|.
DZY wants to perform m operations, each operation can be one of the following:
- Paint all the units with numbers between l and r (both inclusive) with color x.
- Ask the sum of colorfulness of the units between l and r (both inclusive).
Can you help DZY?
Input
The first line contains two space-separated integers n, m (1 ≤ n, m ≤ 105).
Each of the next m lines begins with a integer type (1 ≤ type ≤ 2), which represents the type of this operation.
If type = 1, there will be 3 more integers l, r, x (1 ≤ l ≤ r ≤ n; 1 ≤ x ≤ 108) in this line, describing an operation 1.
If type = 2, there will be 2 more integers l, r (1 ≤ l ≤ r ≤ n) in this line, describing an operation 2.
Output
For each operation 2, print a line containing the answer — sum of colorfulness.
Sample Input
3 3
1 1 2 4
1 2 3 5
2 1 3
8
3 4
1 1 3 4
2 1 1
2 2 2
2 3 3
3
2
1
10 6
1 1 5 3
1 2 7 9
1 10 10 11
1 3 8 12
1 1 10 3
2 1 10
129
Hint
In the first sample, the color of each unit is initially [1, 2, 3], and the colorfulness is [0, 0, 0].
After the first operation, colors become [4, 4, 3], colorfulness become [3, 2, 0].
After the second operation, colors become [4, 5, 5], colorfulness become [3, 3, 2].
So the answer to the only operation of type 2 is 8.
线段树成段更新
1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 using namespace std ; 5 6 #define ls ( o << 1 ) 7 #define rs ( o << 1 | 1 ) 8 #define lson ls , l , m 9 #define rson rs , m + 1 , r10 #define rt o , l , r11 #define root 1 , 1 , n12 #define mid ( ( l + r ) >> 1 )13 #define clear( a , x ) memset ( a , x , sizeof a )14 15 typedef long long LL ;16 17 const int MAXN = 100005 ;18 19 int set[MAXN << 2] ;20 LL sum[MAXN << 2] ;21 LL add[MAXN << 2] ;22 23 void pushUp ( int o , int l , int r ) {24 set[o] = ( set[ls] == set[rs] ? set[ls] : 0 ) ;25 sum[o] = sum[ls] + sum[rs] ;26 }27 28 void pushDown ( int o , int l , int r ) {29 int m = mid ;30 if ( set[o] ) set[ls] = set[rs] = set[o] ;31 if ( add[o] ) {32 sum[ls] += add[o] * ( m - l + 1 ) ;33 add[ls] += add[o] ;34 sum[rs] += add[o] * ( r - m ) ;35 add[rs] += add[o] ;36 add[o] = 0 ;37 }38 }39 40 void build ( int o , int l , int r ) {41 add[o] = set[o] = sum[o] = 0 ;42 if ( l == r ) {43 set[o] = l ;44 return ;45 }46 int m = mid ;47 build ( lson ) ;48 build ( rson ) ;49 }50 51 void update ( int x , int L , int R , int o , int l , int r ) {52 if ( L <= l && r <= R ) {53 if ( set[o] ) {54 add[o] += abs ( x - set[o] ) ;55 sum[o] += ( LL ) abs ( x - set[o] ) * ( r - l + 1 ) ;56 set[o] = x ;57 return ;58 }59 }60 pushDown ( rt ) ;61 int m = mid ;62 if ( L <= m ) update ( x , L , R , lson ) ;63 if ( m < R ) update ( x , L , R , rson ) ;64 pushUp ( rt ) ;65 }66 67 LL query ( int L , int R , int o , int l , int r ) {68 if ( L <= l && r <= R ) return sum[o] ;69 pushDown ( rt ) ;70 int m = mid ;71 LL ans = 0 ;72 if ( L <= m ) ans += query ( L , R , lson ) ;73 if ( m < R ) ans += query ( L , R , rson ) ;74 return ans ;75 }76 77 void work () {78 int n , m ;79 int type , l , r , x ;80 while ( ~scanf ( "%d%d" , &n , &m ) ) {81 build ( root ) ;82 while ( m -- ) {83 scanf ( "%d%d%d" , &type , &l , &r ) ;84 if ( type == 1 ) {85 scanf ( "%d" , &x ) ;86 update ( x , l , r , root ) ;87 }88 else printf ( "%I64d\n" , query ( l , r , root ) ) ;89 }90 }91 }92 93 int main () {94 work () ;95 return 0 ;96 }
Description
DZY loves chessboard, and he enjoys playing with it.
He has a chessboard of n rows and m columns. Some cells of the chessboard are bad, others are good. For every good cell, DZY wants to put a chessman on it. Each chessman is either white or black. After putting all chessmen, DZY wants that no two chessmen with the same color are on two adjacent cells. Two cells are adjacent if and only if they share a common edge.
You task is to find any suitable placement of chessmen on the given chessboard.
Input
The first line contains two space-separated integers n and m(1 ≤ n, m ≤ 100).
Each of the next n lines contains a string of m characters: the j-th character of the i-th string is either "." or "-". A "." means that the corresponding cell (in the i-th row and the j-th column) is good, while a "-" means it is bad.
Output
Output must contain n lines, each line must contain a string of m characters. The j-th character of the i-th string should be either "W", "B" or "-". Character "W" means the chessman on the cell is white, "B" means it is black, "-" means the cell is a bad cell.
If multiple answers exist, print any of them. It is guaranteed that at least one answer exists.
Sample Input
1 1
.
B
2 2
..
..
BW
WB
3 3
.-.
---
--.
B-B
---
--B
Hint
In the first sample, DZY puts a single black chessman. Of course putting a white one is also OK.
In the second sample, all 4 cells are good. No two same chessmen share an edge in the sample output.
In the third sample, no good cells are adjacent. So you can just put 3 chessmen, no matter what their colors are.
先暴力出一个相邻都不同颜色的表，‘.‘根据表输出结果，‘-‘直接输出‘-‘。
#include<stdio.h>#define maxn 109int map[maxn][maxn];void init(){ int i,j,t; for(i = 0;i<maxn;i++) { if(i%2) t=1; else t=0; for(j=0;j<maxn;j++) { map[i][j]=t; t=!t; } }}int main(){ int i,j; init(); int n,m; char ss; while(~scanf("%d %d",&n,&m)) for(i = 0;i<n;i++) { getchar(); for(j=0;j<m;j++) { ss=getchar(); if(ss == ‘-‘) printf("-"); else printf("%c",map[i][j]?‘B‘:‘W‘); } printf("\n"); } return 0;}
Description
DZY loves chemistry, and he enjoys mixing chemicals.
DZY has n chemicals, and m pairs of them will react. He wants to pour these chemicals into a test tube, and he needs to pour them in one by one, in any order.
Let‘s consider the danger of a test tube. Danger of an empty test tube is 1. And every time when DZY pours a chemical, if there are already one or more chemicals in the test tube that can react with it, the danger of the test tube will be multiplied by 2. Otherwise the danger remains as it is.
Find the maximum possible danger after pouring all the chemicals one by one in optimal order.
Input
The first line contains two space-separated integers n and m
.
Each of the next m lines contains two space-separated integers xi and yi(1 ≤ xi < yi ≤ n). These integers mean that the chemical xiwill react with the chemical yi. Each pair of chemicals will appear at most once in the input.
Consider all the chemicals numbered from 1 to n in some order.
Output
Print a single integer — the maximum possible danger.
Sample Input
1 0
1
2 1
1 2
2
3 2
1 2
2 3
4
题目大意：有n种化学物质跟m种反应关系，试管初始的危险系数为1，每次往试管中添加物质，若与前面的物质发生了化学反应那么危险系数乘以2，求最大危险系数。
解题思路：用并查集找出各个集合，每个结合的最大发生反应次数为它物质的个数-1。换种思路，就是求s=物质的总数-集合个数,结果为2^t。
1 #include<stdio.h> 2 #define maxn 105 3 typedef long long LL; 4 int fa[maxn]; 5 int find(int x) 6 { 7 while(fa[x] != x) 8 { 9 x = fa[x];10 }11 return x;12 }13 void merge(int x,int y)14 {15 int a = find(x);16 int b = find(y);17 if(a != b)18 fa[a] = b;19 }20 21 int main()22 {23 int n,m,i,a,b;24 scanf("%d%d",&n,&m);25 for(i=0;i<maxn;i++)26 fa[i] = i;27 for(i = 0;i<m;i++)28 {29 scanf("%d%d",&a,&b);30 merge(a,b);31 }32 int t=0;33 LL ans =1;34 for(i = 1;i<=n;i++)35 {36 if(fa[i] == i)t++;37 }38 ans = ans<<(n-t);39 printf("%lld\n",ans);40 return 0;41 }
Description
As we know, DZY loves playing games. One day DZY decided to play with a n × m matrix. To be more precise, he decided to modify the matrix with exactly k operations.
Each modification is one of the following:
- Pick some row of the matrix and decrease each element of the row by p. This operation brings to DZY the value of pleasure equal to the sum of elements of the row before the decreasing.
- Pick some column of the matrix and decrease each element of the column by p. This operation brings to DZY the value of pleasure equal to the sum of elements of the column before the decreasing.
DZY wants to know: what is the largest total value of pleasure he could get after performing exactly k modifications? Please, help him to calculate this value.
Input
The first line contains four space-separated integers n, m, k and p(1 ≤ n, m ≤ 103; 1 ≤ k ≤ 106; 1 ≤ p ≤ 100).
Then n lines follow. Each of them contains m integers representing aij (1 ≤ aij ≤ 103) — the elements of the current row of the matrix.
Output
Output a single integer — the maximum possible total pleasure value DZY could get.
Sample Input
2 2 2 2
1 3
2 4
11
2 2 5 2
1 3
2 4
11
Hint
For the first sample test, we can modify: column 2, row 2. After that the matrix becomes:
1 1
0 0
For the second sample test, we can modify: column 2, row 2, row 1, column 1, column 2. After that the matrix becomes:
-3 -3
-2 -2
题目大意：一个n*m的矩阵有k次操作,每次操作选一行或一列同时减去p操作的价值为这一行或一列没操作之前的和,求最大的价值。
解题思路：一共操作k次，可以设行操作i次,列操作k-i次，每次都是最优操作即选那一行或那一列的和最大的，对i从0到k枚举结果。
1 #include <iostream> 2 #include <cstdio> 3 #include <queue> 4 #include <cstring> 5 using namespace std; 6 7 typedef __int64 LL; 8 const int maxn=1005; 9 const int maxm=1000005;10 int map[maxn][maxn];11 LL C[maxm],R[maxm];12 priority_queue<LL>sc,sr;13 LL max(LL a,LL b){return a>b?a:b;}14 15 int main()16 {17 int i,j,n,m,k,p;18 LL ans,s;19 while(~scanf("%d %d %d %d",&n,&m,&k,&p))20 {21 while(!sc.empty()) sc.pop();22 while(!sr.empty()) sr.pop();23 memset(C,0,sizeof(C));24 memset(R,0,sizeof(R));25 for(i=0;i<n;i++)26 for(j=0;j<m;j++)27 scanf("%d",&map[i][j]);28 for(i=0;i<n;i++)29 {30 s=0;31 for(j=0;j<m;j++)32 s+=map[i][j];33 sc.push(s);34 }35 for(j=0;j<m;j++)36 {37 s=0;38 for(i=0;i<n;i++)39 s+=map[i][j];40 sr.push(s);41 }42 for(i=1;i<=k;i++)43 {44 s=sc.top();sc.pop();45 C[i]=C[i-1]+s;46 s=s-p*m;47 sc.push(s);48 }49 for(i=1;i<=k;i++)50 {51 s=sr.top();sr.pop();52 R[i]=R[i-1]+s;53 s=s-p*n;54 sr.push(s);55 }56 ans=-1e18;57 for(i=0;i<=k;i++)58 ans=max(ans,C[i]+R[k-i]-(LL)i*(k-i)*p);59 printf("%I64d\n",ans);60 }61 return 0;62 }
Description
Artem has an array of n positive integers. Artem decided to play with it. The game consists of n moves. Each move goes like this. Artem chooses some element of the array and removes it. For that, he gets min(a, b) points, where a and b are numbers that were adjacent with the removed number. If the number doesn‘t have an adjacent number to the left or right, Artem doesn‘t get any points.
After the element is removed, the two parts of the array glue together resulting in the new array that Artem continues playing with. Borya wondered what maximum total number of points Artem can get as he plays this game.
Input
The first line contains a single integer n(1 ≤ n ≤ 5·105) — the number of elements in the array. The next line contains n integers ai(1 ≤ ai ≤ 106) — the values of the array elements.
Output
In a single line print a single integer — the maximum number of points Artem can get.
Sample Input
5
3 1 5 2 6
11
5
1 2 3 4 5
6
5
1 100 101 100 1
102
题目大意：给一个n的整数序列，每次删除一个数此次操作的价值为它左右两个数间的较小值，若左边或右边没有数那此次操作的价值为0，求最大价值。
解题思路：本着这波不亏的贪心思想，先从那些删了这个数不亏的开始，即左右两个数均大于等于它。当这样的好事做完后，新序列有三种情况（1）单调递增（2）单调递减（3）先增后减。这种情况价值最大的情况为序列和减去最大的两个数（绝对不坑）。
1 #include <iostream> 2 #include <cstdio> 3 #include <algorithm> 4 using namespace std; 5 6 typedef long long LL; 7 inline int min(int a,int b){ return a<b?a:b;} 8 const int maxn=500005; 9 int n,f[maxn];10 11 int main()12 {13 int i,top,x;14 LL ans;15 while(~scanf("%d",&n))16 {17 ans=0;top=0;18 for(i=0;i<n;i++)19 {20 scanf("%d",&x); 21 while(top>1&&f[top-2]>=f[top-1]&&x>=f[top-1]) 22 { 23 ans+=min(x,f[top-2]); 24 top--; 25 } 26 f[top++]=x; 27 }28 sort(f,f+top);29 for(i=0;i<top-2;i++) ans+=f[i];30 printf("%lld\n",ans);31 }32 return 0;33 }