Codeforces Round #744 (Div. 3)
admin
|
|
308
|
Codeforces

1501 字
|
37 分钟

Codeforces Round #744 (Div. 3)

A. Casimir's String Solitaire

题目描述：

一个串，可以同时消去一个A和一个B，也可以同时消去一个B和一个C，可以进行无数次，问最终能不能消掉所有的字符

思路：

如果A+C = B，就可以，否则不行

// Author: Chelsea
// 2021.09.28
#include<map>
#include<set>
#include<stack>
#include<queue>
#include<cmath>
#include<bitset>
#include<cstdio>
#include<string>
#include<vector>
#include<sstream>
#include<cstring>
#include<stdlib.h>
#include<iostream>
#include<algorithm>
#include "unordered_map"
using namespace std;

#pragma GCC optimize("Ofast")
#pragma GCC target("fma,sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
#pragma GCC optimize("unroll-loops")

#define eps 1e-8
#define endl '\n'
#define inf 0x3f3f3f3f
#define NMAX 500 + 50
#define MAX 1000000 + 50
//#define mod 998244353
#define lowbit(x) (x & (-x))
#define sd(n) scanf("%lld",&n)
#define sdd(n,m) scanf("%lld %lld",&n,&m)
#define pd(n) printf("%d\n", (n))
#define pdd(n,m) printf("%d %d\n",n, m)
#define sddd(n,m,z) scanf("%lld %lld %lld",&n,&m,&z)
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define mem(a,b) memset((a),(b),sizeof(a))
#define m_p(a,b) make_pair(a, b)

typedef  long long ll;
typedef pair <int,int> pii;
typedef unsigned long long ull;
//不开longlong见祖宗!不看范围见祖宗!
inline int IntRead(){char ch = getchar();int s = 0, w = 1;while(ch < '0' || ch > '9'){if(ch == '-') w = -1;ch = getchar();}while(ch >= '0' && ch <= '9'){s = s * 10 + ch - '0';ch = getchar();}return s * w;}


int n, m, k;
string s;


void work(){
    cin>>s;
    n = m = k = 0;
    for(int i = 0; i < s.size(); ++i){
        if(s[i] == 'A')++n;
        else if(s[i] == 'B')++m;
        else ++k;
    }
    if(m == n + k)cout<<"YES\n";
    else cout<<"NO\n";
}

int main(){
    int tt;cin>>tt;
    for(int _t = 1; _t <= tt; ++_t){
//        printf("Case #%d: ", _t);
        work();
    }
    return 0;
}

B. Shifting Sort

题目描述：

给n个数，你可以挑任意一个区间，将他们看成一个环，在环的基础上将这个区间的每个数都向左移动d次，问如何进行操作使得最终的数组是升序的，且操作次数小于等于n，输出每次操作的l，r，d

思路：

直接模拟第 i 位应该放谁来统计即可

每次都从[i,n]中挑最小的数去放到第 i 位，此时输出的就是{i, pos, pos – i}，pos即i到n中最小数的位置

然后暴力修改[i, pos-1]，将每个数都往后移动一位

// Author: Chelsea
// 2021.09.28
#include<map>
#include<set>
#include<stack>
#include<queue>
#include<cmath>
#include<bitset>
#include<cstdio>
#include<string>
#include<vector>
#include<sstream>
#include<cstring>
#include<stdlib.h>
#include<iostream>
#include<algorithm>
#include "unordered_map"
using namespace std;

#pragma GCC optimize("Ofast")
#pragma GCC target("fma,sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
#pragma GCC optimize("unroll-loops")

#define eps 1e-8
#define endl '\n'
#define inf 0x3f3f3f3f
#define NMAX 500 + 50
#define MAX 1000000 + 50
//#define mod 998244353
#define lowbit(x) (x & (-x))
#define sd(n) scanf("%d",&n)
#define sdd(n,m) scanf("%d %d",&n,&m)
#define pd(n) printf("%d\n", (n))
#define pdd(n,m) printf("%d %d\n",n, m)
#define sddd(n,m,z) scanf("%lld %lld %lld",&n,&m,&z)
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define mem(a,b) memset((a),(b),sizeof(a))
#define m_p(a,b) make_pair(a, b)

typedef  long long ll;
typedef pair <int,int> pii;
typedef unsigned long long ull;
//不开longlong见祖宗!不看范围见祖宗!
inline int IntRead(){char ch = getchar();int s = 0, w = 1;while(ch < '0' || ch > '9'){if(ch == '-') w = -1;ch = getchar();}while(ch >= '0' && ch <= '9'){s = s * 10 + ch - '0';ch = getchar();}return s * w;}

int n, x;
int tr[MAX];
int minx, pos;

struct ran{
    int l, r, d;
};

void work()
{
    sd(n);
    for(int i = 1; i <= n; ++i)sd(tr[i]);
    vector<ran>v;
    for(int i = 1; i <= n; ++i){
        minx = tr[i];pos = i;
        for(int j = i + 1; j <= n; ++j){
            if(tr[j] < minx){
                minx = tr[j];
                pos = j;
            }
        }
        if(pos == i)continue;
        v.push_back({i, pos, pos - i});
        for(int j = pos; j >= i + 1; --j){
            tr[j] = tr[j - 1];
        }
    }
    cout<<v.size()<<endl;
    for(int i = 0; i < v.size(); ++i)cout<<v[i].l<<' '<<v[i].r<<' '<<v[i].d<<endl;
}

int main(){
    int tt;cin>>tt;
    for(int _t = 1; _t <= tt; ++_t){
//        printf("Case #%d: ", _t);
        work();
    }
    return 0;
}

C. Ticks

题目描述：

给定n * m的图，* 代表此处为黑色，其他的为白色

你对一张全白色的图进行无数次如下的操作：是挑一个点，沿左上方与右上方两个方向都斜着染至少k个点，左上与右上染色的数量必须相同。

重复染色还是黑色

问你能不能将白图染成给定的图

思路：

对于给定的图，枚举每个点能向左上与右上同时能染色的最大的数量，判段如果大于等于k，就染掉

最后将染成的图与给定的图进行比较

// Author: Chelsea
// 2021.09.28
#include<map>
#include<set>
#include<stack>
#include<queue>
#include<cmath>
#include<bitset>
#include<cstdio>
#include<string>
#include<vector>
#include<sstream>
#include<cstring>
#include<stdlib.h>
#include<iostream>
#include<algorithm>
using namespace std;

//#pragma GCC optimize("Ofast")
//#pragma GCC target("fma,sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
//#pragma GCC optimize("unroll-loops")

#define eps 1e-8
#define endl '\n'
#define inf 0x3f3f3f3f
#define NMAX 1000 + 50
#define MAX 100000 + 50
#define ls p<<1
#define rs p<<1|1
//#define mod 1000000007
#define lowbit(x) (x & (-x))
#define sd(n) scanf("%lld",&n)
#define sdd(n,m) scanf("%lld %lld",&n,&m)
#define pd(n) printf("%d\n", (n))
#define pdd(n,m) printf("%d %d\n",n, m)
#define sddd(n,m,z) scanf("%lld %lld %lld",&n,&m,&z)
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define mem(a,b) memset((a),(b),sizeof(a))
#define m_p(a,b) make_pair(a, b)

typedef  long long ll;
typedef pair <int,int> pii;
typedef unsigned long long ull;
//不开longlong见祖宗!不看范围见祖宗!
inline int IntRead(){char ch = getchar();int s = 0, w = 1;while(ch < '0' || ch > '9'){if(ch == '-') w = -1;ch = getchar();}while(ch >= '0' && ch <= '9'){s = s * 10 + ch - '0';ch = getchar();}return s * w;}


int n, m, k;
char tr[50][50];
char ans[50][50];

bool judge(int x, int y){
    if(x > n || x < 1 || y > m || y < 1)return false;
    if(tr[x][y] == '.')return false;
    return true;
}

int xx, yy;

void update(int x, int y){
    int num1 = 0;
    int num2 = 0;
    for(int i = 1; ; ++i){
        xx = x - i;
        yy = y - i;
        if(judge(xx, yy))++num1;
        else break;
    }
    for(int i = 1; ; ++i){
        xx = x - i;
        yy = y + i;
        if(judge(xx, yy))++num2;
        else break;
    }
    int num = min(num1, num2);
    if(num >= k){
        ans[x][y] = '*';
        for(int i = 1; i <= num; ++i){
            xx = x - i;
            yy = y - i;
            ans[xx][yy] = '*';
        }
        for(int i = 1; i <= num; ++i){
            xx = x - i;
            yy = y + i;
            ans[xx][yy] = '*';
        }
    }
}

void work(){
    mem(ans, 0);
    cin>>n>>m>>k;
    for(int i = 1; i <= n; ++i)for(int j = 1; j <= m; ++j)cin>>tr[i][j];
    for(int i = 1; i <= n; ++i){
        for(int j = 1; j <= m; ++j){
            if(tr[i][j] == '*')update(i, j);
        }
    }
    for(int i = 1; i <= n; ++i){
        for(int j = 1; j <= m; ++j){
            if(ans[i][j] != '*')ans[i][j] = '.';
        }
    }
    for(int i = 1; i <= n; ++i){
        for(int j = 1; j <= m; ++j){
            if(ans[i][j] != tr[i][j]){
                cout<<"NO\n";
                return;
            }
        }
    }
    cout<<"YES\n";
}

int main(){
    int tt;cin>>tt;
    for(int _t = 1; _t <= tt; ++_t){
//        printf("Case #%d: ", _t);
        work();
    }
    return 0;
}

D. Productive Meeting

题目描述：

n个人，每个人有ai个物品，每次都可以挑任意两个ai非0的人，使得他们的ai减一，问最多能进行多少次这样的操作，并输出每次操作的两个人的编号

思路：

开个优先队列，每次都挑最大的两个出来，减1，再放回去，记录ans即可

// Author: Chelsea
// 2021.09.28
#include<map>
#include<set>
#include<stack>
#include<queue>
#include<cmath>
#include<bitset>
#include<cstdio>
#include<string>
#include<vector>
#include<sstream>
#include<cstring>
#include<stdlib.h>
#include<iostream>
#include<algorithm>
#include "unordered_map"
using namespace std;

#pragma GCC optimize("Ofast")
#pragma GCC target("fma,sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
#pragma GCC optimize("unroll-loops")

#define eps 1e-8
#define endl '\n'
#define inf 0x3f3f3f3f
#define NMAX 500 + 50
#define MAX 1000000 + 50
//#define mod 998244353
#define lowbit(x) (x & (-x))
#define sd(n) scanf("%d",&n)
#define sdd(n,m) scanf("%d %d",&n,&m)
#define pd(n) printf("%d\n", (n))
#define pdd(n,m) printf("%d %d\n",n, m)
#define sddd(n,m,z) scanf("%lld %lld %lld",&n,&m,&z)
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define mem(a,b) memset((a),(b),sizeof(a))
#define m_p(a,b) make_pair(a, b)

typedef  long long ll;
typedef pair <int,int> pii;
typedef unsigned long long ull;
//不开longlong见祖宗!不看范围见祖宗!
inline int IntRead(){char ch = getchar();int s = 0, w = 1;while(ch < '0' || ch > '9'){if(ch == '-') w = -1;ch = getchar();}while(ch >= '0' && ch <= '9'){s = s * 10 + ch - '0';ch = getchar();}return s * w;}

int n, x;
struct ran{
    int id, val;
    inline bool operator < (const ran &x)const{
           return val < x.val;
       }
};

void work()
{
    priority_queue<ran>q;
    sd(n);
    for(int i = 1; i <= n; ++i){
        sd(x);
        if(x != 0)q.push({i, x});
    }
    vector<pii>v;
    vector<int>num;
    ll sum = 0;
    while (q.size() > 1) {
        ran a = q.top();q.pop();
        ran b = q.top();q.pop();
        --a.val;--b.val;
        ++sum;
        v.push_back(m_p(a.id, b.id));
        if(a.val != 0)q.push(a);
        if(b.val != 0)q.push(b);
    }
    cout<<sum<<endl;
    for(int i = 0; i < v.size(); ++i){
        cout<<v[i].first<<' '<<v[i].second<<endl;
    }
    
}

int main(){
    int tt;cin>>tt;
    for(int _t = 1; _t <= tt; ++_t){
//        printf("Case #%d: ", _t);
        work();
    }
    return 0;
}

E1. Permutation Minimization by Deque

题目描述：

给定n个数，按顺序他们插进双端队列的头或者尾，问如果插能使得字典序最小

思路：

直接模拟就行

如果ai<队列的头，就塞到队头，否则就塞到队尾

// Author: Chelsea
// 2021.09.23
#include<map>
#include<set>
#include<stack>
#include<queue>
#include<cmath>
#include<bitset>
#include<cstdio>
#include<string>
#include<vector>
#include<sstream>
#include<cstring>
#include<stdlib.h>
#include<iostream>
#include<algorithm>
#include "unordered_map"
using namespace std;

#pragma GCC optimize("Ofast")
#pragma GCC target("fma,sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
#pragma GCC optimize("unroll-loops")

#define eps 1e-8
#define endl '\n'
#define inf 0x3f3f3f3f
#define NMAX 500 + 50
#define MAX 1000000 + 50
//#define mod 998244353
#define lowbit(x) (x & (-x))
#define sd(n) scanf("%d",&n)
#define sdd(n,m) scanf("%d %d",&n,&m)
#define pd(n) printf("%d\n", (n))
#define pdd(n,m) printf("%d %d\n",n, m)
#define sddd(n,m,z) scanf("%lld %lld %lld",&n,&m,&z)
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define mem(a,b) memset((a),(b),sizeof(a))
#define m_p(a,b) make_pair(a, b)

typedef  long long ll;
typedef pair <int,int> pii;
typedef unsigned long long ull;
//不开longlong见祖宗!不看范围见祖宗!
inline int IntRead(){char ch = getchar();int s = 0, w = 1;while(ch < '0' || ch > '9'){if(ch == '-') w = -1;ch = getchar();}while(ch >= '0' && ch <= '9'){s = s * 10 + ch - '0';ch = getchar();}return s * w;}

int n, x;

void work()
{
    deque<int>q;
    sd(n);
    for(int i = 1; i <= n; ++i){
        sd(x);
        if(i == 1){
            q.push_back(x);
            continue;
        }
        if(x < q.front())q.push_front(x);
        else q.push_back(x);
    }
    for(int i = 0; i < q.size();++i)cout<<q[i]<<' ';
    cout<<endl;
}

int main(){
    int tt;cin>>tt;
    for(int _t = 1; _t <= tt; ++_t){
//        printf("Case #%d: ", _t);
        work();
    }
    return 0;
}

E2. Array Optimization by Deque

题目描述：

和上面差不多，你可以将ai插到队列的头或尾，问进行操作后得到最小的逆序对的数量是多少

思路：

树状数组+贪心

对一个要插入的数x来说，min（小于x的数量，大于x的数量）即为此次插入贡献的逆序对数

// Author: Chelsea
// 2021.09.28
#include<map>
#include<set>
#include<stack>
#include<queue>
#include<cmath>
#include<bitset>
#include<cstdio>
#include<string>
#include<vector>
#include<sstream>
#include<cstring>
#include<stdlib.h>
#include<iostream>
#include<algorithm>
#include "unordered_map"
using namespace std;

#pragma GCC optimize("Ofast")
#pragma GCC target("fma,sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
#pragma GCC optimize("unroll-loops")

#define eps 1e-8
#define endl '\n'
#define inf 0x3f3f3f3f
#define NMAX 500 + 50
#define MAX 1000000 + 50
//#define mod 998244353
#define lowbit(x) (x & (-x))
#define sd(n) scanf("%d",&n)
#define sdd(n,m) scanf("%d %d",&n,&m)
#define pd(n) printf("%d\n", (n))
#define pdd(n,m) printf("%d %d\n",n, m)
#define sddd(n,m,z) scanf("%lld %lld %lld",&n,&m,&z)
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define mem(a,b) memset((a),(b),sizeof(a))
#define m_p(a,b) make_pair(a, b)

typedef  long long ll;
typedef pair <int,int> pii;
typedef unsigned long long ull;
//不开longlong见祖宗!不看范围见祖宗!
inline int IntRead(){char ch = getchar();int s = 0, w = 1;while(ch < '0' || ch > '9'){if(ch == '-') w = -1;ch = getchar();}while(ch >= '0' && ch <= '9'){s = s * 10 + ch - '0';ch = getchar();}return s * w;}

int n, x;
ll tot, ans;

int tr[MAX];
int tt[MAX];

map<int, int>mp;

int ar[MAX], br[MAX];

inline void update1(int i){
    for(;i <= tot; i += lowbit(i))++ar[i];
    return;
}

inline ll getans1(int i){
    ll res = 0;
    for(; i; i -= lowbit(i))res += ar[i];
    return res;
}

inline void update2(int i){
    for(; i; i -= lowbit(i))++br[i];
    return;
}

inline ll getans2(int i){
    ll res = 0;
    for(;i <= tot;i += lowbit(i))res += br[i];
    return res;
}

inline void init(){
    mem(ar, 0);
    mem(br, 0);
    mp.clear();
    ans = tot = 0;
}

void work()
{
    init();
    sd(n);
    for(int i = 1; i <= n; ++i){
        sd(tr[i]);
        tt[i] = tr[i];
    }
    sort(tt + 1, tt + 1 + n);
    for(int i = 1; i <= n; ++i){
        if(!mp[tt[i]])mp[tt[i]] = ++tot;
    }
    for(int i = 1; i <= n; ++i){
        if(getans1(mp[tr[i]] - 1) < getans2(mp[tr[i]] + 1))ans += getans1(mp[tr[i]] - 1);
        else ans += getans2(mp[tr[i]] + 1);
        update1(mp[tr[i]]);
        update2(mp[tr[i]]);
    }
    cout<<ans<<endl;
}

int main(){
    int tt;cin>>tt;
    for(int _t = 1; _t <= tt; ++_t){
//        printf("Case #%d: ", _t);
        work();
    }
    return 0;
}

F. Array Stabilization (AND version)

思路：

转换成图论来解决

因为只有0的移动到了1的位置才能使得1变成0，所以将所有0的位置看成源点，去跑SPFA，最后取max判断即可

#include<map>
#include<set>
#include<stack>
#include<queue>
#include<cmath>
#include<bitset>
#include<cstdio>
#include<string>
#include<vector>
#include<sstream>
#include<cstring>
#include<stdlib.h>
#include<iostream>
#include<algorithm>
using namespace std;

//#pragma GCC optimize("Ofast")
//#pragma GCC target("fma,sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
//#pragma GCC optimize("unroll-loops")

#define eps 1e-8
#define endl '\n'
#define inf 0x3f3f3f3f
#define NMAX 1000 + 50
#define MAX 1000000 + 50
#define ls p<<1
#define rs p<<1|1
//#define mod 1000000007
#define lowbit(x) (x & (-x))
#define sd(n) scanf("%d",&n)
#define sdd(n,m) scanf("%d %d",&n,&m)
#define pd(n) printf("%d\n", (n))
#define pdd(n,m) printf("%d %d\n",n, m)
#define sddd(n,m,z) scanf("%lld %lld %lld",&n,&m,&z)
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define mem(a,b) memset((a),(b),sizeof(a))
#define m_p(a,b) make_pair(a, b)

typedef  long long ll;
typedef pair <int,int> pii;
typedef unsigned long long ull;
//不开longlong见祖宗!不看范围见祖宗!
inline int IntRead(){char ch = getchar();int s = 0, w = 1;while(ch < '0' || ch > '9'){if(ch == '-') w = -1;ch = getchar();}while(ch >= '0' && ch <= '9'){s = s * 10 + ch - '0';ch = getchar();}return s * w;}

int n, m, k, d, x;
int dis[MAX];
bool vis[MAX];
queue<int>q;

void SPFA(){
    while (!q.empty()) {
        int u = q.front();q.pop();
        vis[u] = 0;
        int v = (u - 1 + d) % n + 1;
        if(dis[v] > dis[u] + 1){
            dis[v] = dis[u] + 1;
            if(!vis[v]){
                vis[v] = 1;
                q.push(v);
            }
        }
    }
}

void work(){
    sdd(n, d);
    mem(dis, inf);
    mem(vis, 0);
    while (!q.empty()) {
        q.pop();
    }
    for(int i = 1; i <= n; ++i){
        sd(x);
        if(!x){
            q.push(i);
            vis[i] = 1;
            dis[i]   = 0;
        }
    }
    SPFA();
    int ans = 0;
    for(int i = 1; i <= n; ++i){
        ans = max(ans, dis[i]);
    }
    if(ans >= inf)cout<<-1<<endl;
    else cout<<ans<<endl;
    
}

int main(){
    int tt;cin>>tt;
    for(int _t = 1; _t <= tt; ++_t){
//        printf("Case #%d: ", _t);
        
        work();
    }
    return 0;
}

 

博客内容均系原创，未经允许严禁转载！
cf
暂无评论

发送评论 编辑评论 


				

			

						

				

					

						

							

								
							

							
						

					

				

				

					

						

							

								
							

							
						

					

				

				

					

						

							

								
							

							
							
													

					

				

			

			
			

				

					
				

			

				

											

							
							
						

																					

							
							
						

										
					
											
						

	

		
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
（╯‵□′）╯︵┴─┴
￣﹃￣
(/ω＼)
∠( ᐛ 」∠)＿
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ｀)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ(￣∇￣o)
ヾ(´･ ･｀｡)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò｡)
Σ(っ °Д °;)っ
( ,,´･ω･)ﾉ"(´っω･｀｡)
╮(╯▽╰)╭
o(*////▽////*)q
＞﹏＜
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
	

	

		
颜文字
Emoji
小恐龙
花!
	


									

			

			
			
		

	






上一篇
下一篇 

                    

                    
			        推荐文章
		            

		            

							
Codeforces Round 728 (Div. 1) A. Great Graphs「思维 + 贪心 + 前缀和优化」

							
							

							
Codeforces Round #779 (Div. 2)

							
							

							
Codeforces Round 731 (Div. 3) E. Air Conditioners「思维 + dp」或「思维 + bfs + 堆优化」

							
							

							
Codeforces Round #832 (Div. 2)「D 思维 + 异或前缀和 + 奇偶二分优化」

							
							

							
Codeforces Round #740 (Div. 2)