Codeforces Round #744 (Div. 3) A-F 题解

第一次接近前百纪念

这次的题意就不再赘述了
大概说一下方法

A. Casimir’s String Solitaire

思路：
每次都有B
B的数量等于A和C的和即可
时间复杂度：$On$

#include #define fer(i,a,b) for(re i = a ; i <= b ; ++ i)#define der(i,a,b) for(re i = a ; i >= b ; -- i)#define all(x) (x).begin(),(x).end()#define de(x) cout << x << "/n" #define sf(x) scanf("%lld",&x)#define pll pair<int,int> #define re register int#define int long long #define pb push_back#define y second #define x first using namespace std;const int inf = 0x3f3f3f3f3f3f3f3f3f3f3f3f3f3f3f3f ;const int N = 1e6 + 10 , M = 2010 , mod = 1e9 + 7 ;signed main(){    int t ;    cin >> t ;        while(t--)    {        string a ;                int kb = 0 , k = 0 ;                cin >> a ;                for(auto i : a)         {            if(i == "B") kb ++ ;            else k ++ ;        }                if(kb == k) puts("YES") ;        else puts("NO") ;    }    return 0;}

B. Shifting Sort

思路：
倒着做
每次找到最大的一个数，放到最后即可
注意序列是动态的 不过n很小
直接暴力
时间复杂度：$O{n}^2$

#include #define fer(i,a,b) for(re i = a ; i <= b ; ++ i)#define der(i,a,b) for(re i = a ; i >= b ; -- i)#define all(x) (x).begin(),(x).end()#define de(x) cout << x << "/n" #define sf(x) scanf("%lld",&x)#define pll pair<int,int> #define re register int#define int long long #define pb push_back#define y second #define x first using namespace std;const int inf = 0x3f3f3f3f3f3f3f3f3f3f3f3f3f3f3f3f ;const int N = 60 , M = 2010 , mod = 1e9 + 7 ; int n ;int a[N] ;int b[N] ;int c[N] ; struct ai{    int l , r , d ;}q[N] ; signed main(){    int t ;    cin >> t ;    while(t--)    {        cin >> n ;                fer(i,1,n) sf(a[i]) ;                fer(i,1,n) b[i] = a[i] ;                sort(b + 1 , b + 1 + n) ;                int hh = 0 ;                der(i,n,1)        {            int k = 0;            for(int j = i ; j >= 1 ; j --)            {                if(a[j] == b[i])                {                    k = j ;                    break ;                }            }            if(k != 0 && k != i)            {                q[++ hh] = {k,i,1} ;                                fer(i,1,k-1) c[i] = a[i] ;                fer(i,k,n-1) c[i] = a[i+1] ;                c[n] = a[k] ;                memcpy(a,c,sizeof c) ;            }        }                cout << hh << "/n" ;        fer(i,1,hh) cout << q[i].l << " " << q[i].r << " " << q[i].d << "/n" ;            }    return 0;}

C. Ticks

思路：
模拟一下就行
时间复杂度：$Onmk$

#include #define fer(i,a,b) for(re i = a ; i <= b ; ++ i)#define der(i,a,b) for(re i = a ; i >= b ; -- i)#define all(x) (x).begin(),(x).end()#define de(x) cout << x << "/n" #define sf(x) scanf("%lld",&x)#define pll pair<int,int> #define re register int#define int long long #define pb push_back#define y second #define x first using namespace std;const int inf = 0x3f3f3f3f3f3f3f3f3f3f3f3f3f3f3f3f ;const int N = 1e6 + 10 , M = 50 , mod = 1e9 + 7 ; int n, m, k;char s[M][M];bool st[M][M]; bool check(int x, int y){	if(x < 0 || x >= n || y < 0 || y >= m) return 0 ;	else return 1 ;} void get(int x, int y){	int l = 0, r = 0; 	while (check(x - l, y - l) && s[x - l][y - l] == "*")		l ++;	while (check(x - r, y + r) && s[x - r][y + r] == "*")		r ++; 	l --;	r --;	if (min(l, r) >= k) {		for (int i = 0; i <= min(l, r); i++) {			st[x - i][y - i] = 1;			st[x - i][y + i] = 1;		}	}} void solve(){    cin >> n >> m >> k;    	memset(st, 0, sizeof st);		fer(i,0,n-1)		scanf("%s", s[i]); 	fer(i,0,n-1)		fer(j,0,m-1)			if (s[i][j] == "*")				get(i, j); 	bool w = 1;	fer(i,0,n-1)		fer(j,0,m-1)			if (s[i][j] == "*" && st[i][j] == 0)				w = 0; 	if (w)		puts("YES") ;	else		puts("NO") ;}signed main(){	int t ;	cin >> t ;	while (t--) 	{		solve() ;	}	return 0;}

D. Productive Meeting

思路：
注意到a[i]的总和是2e5
直接小根堆每次取出最大的2个–即可

其实这题是以前cf的原题
问的是不输出方案的最大值
记录最大值和总和比较一下即可on

其实每次取出最大的2个不一定是对的
（因为给不出证明）
其实我是想用set取出一大一小一定是对的

但是已经写完了优先队列就不想改了
时间复杂度：$Onlogn$

#include #define fer(i,a,b) for(re i = a ; i <= b ; ++ i)#define der(i,a,b) for(re i = a ; i >= b ; -- i)#define all(x) (x).begin(),(x).end()#define de(x) cout << x << "/n" #define sf(x) scanf("%lld",&x)#define pll pair<int,int> #define re register int#define int long long #define pb push_back#define y second #define x first using namespace std;const int inf = 0x3f3f3f3f3f3f3f3f3f3f3f3f3f3f3f3f ;const int N = 1e6 + 10 , M = 2010 , mod = 1e9 + 7 ;int t ;int n ;int a[N] ;pll ans[N] ;signed main(){    cin >> t ;        while(t--)    {        cin >> n ;            int s = 0 ;                priority_queue<pll> q ;                fer(i,1,n)        {            sf(a[i]) ;            if(a[i]) q.push({a[i],i}) ;        }                int hh = 0 ;                while(q.size() >= 2)        {            auto t1 = q.top() ;            q.pop() ;                        auto t2 = q.top() ;            q.pop() ;                        ans[ ++ hh] = {t1.y,t2.y} ;                        t1.x -- , t2.x -- ;            if(t1.x) q.push({t1.x,t1.y}) ;            if(t2.x) q.push({t2.x,t2.y}) ;        }                de(hh) ;                fer(i,1,hh)        {            cout << ans[i].x << " " << ans[i].y << "/n" ;        }    }    return 0;}

E1. Permutation Minimization by Deque

思路：
用duque直接模拟
小的放前面，大的放后面即可
时间复杂度：$On$

#include #define fer(i,a,b) for(re i = a ; i <= b ; ++ i)#define der(i,a,b) for(re i = a ; i >= b ; -- i)#define all(x) (x).begin(),(x).end()#define de(x) cout << x << "/n" #define sf(x) scanf("%lld",&x)#define 
                 

                                                                                                                    
                         混合云
                                             
                         私有云
                                                                                                                                                 
                                      
                     
                    
                                                                                               题解
                                                                                                           oj题解
                                                                                                           round()
                                                                                                           ROUND