2021CCPC桂林
Dashboard - The 2021 CCPC Guilin Onsite (XXII Open Cup, Grand Prix of EDG) - Codeforces
A - A Hero Named Magnus
看不懂题目
#include <bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;
void solve()
{
int x;
cin >> x;
int ans = (x-1)*2 + 1;
cout << ans << endl;
}
signed main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int T = 1;
cin >> T;
while(T--) solve();
return 0;
}
I - PTSD
贪心，从后往前能拿就拿
#include <bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;
void solve()
{
int n;
cin >> n;
string s;
cin >> s;
int cnt1 = 0 , cnt0 = 0;
int ans = 0;
for(int i=n-1;i>=0;i--)
{
if(s[i]=='0')
{
cnt0++;
}
else
{
if(!cnt0)
{
cnt0++;
}
else
{
cnt0--;
ans+= (i+1);
}
}
}
cout << ans << endl;
}
signed main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int T = 1;
cin >> T;
while(T--) solve();
return 0;
}
G - Occupy the Cities
二分+贪心
当回合数为n时，s[i]=='1'的话，覆盖范围为[i-n,i+n-1]或[i-n+1,i+n];
#include <bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;
typedef pair<int,int> PII; typedef pair<double,double> PDD;
const int inf = 0x4f4f4f4f;
int n;
string s;
bool check(int len)
{
vector<int> b(n+10,0);
int x = len - 1;
for(int i=1;i<=n;i++)
{
if(s[i]=='0') continue;
int l = max(i-x,1ll);
int r = min(i+x+1,n+1);
b[l]++;
b[r]--;
}
for(int i=1;i<=n;i++) b[i] += b[i-1];
for(int i=1;i<=n;i++)
{
if(s[i]=='1')
{
if(i-len>0&&b[i-len]==0)
{
b[i-len]=1;
continue;
}
if(i+len<=n&&b[i+len]==0)
{
b[i+len]=1;
}
}
}
//for(int i=1;i<=n;i++) cout << i << " " << b[i] << endl;
for(int i=1;i<=n;i++)
if(b[i]==0) return false;
return true;
}
void solve()
{
cin >> n >> s;
s = " " + s + " ";
int l = 0 , r = n;
int ans = 1e18;
//check(2);
while(l<=r)
{
int mid = l + r >> 1;
//cout << mid << endl;
if(check(mid)) r = mid - 1 , ans = min(ans,mid);
else l = mid + 1;
}
cout << ans << endl;
}
signed main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int T = 1;
cin >> T;
while(T--) solve();
return 0;
}
E - Buy and Delete
怎么有人能把greater写成less
显然如果所有的边的val都比c大（一条边都买不了），答案为0
买的起环 则答案为2
买不起环 答案为1
跑一下最短路然后找有没有环的val小于c即可
#include <bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;
typedef pair<int,int> PII; typedef pair<double,double> PDD;
const int inf = 0x4f4f4f4f;
const int N = 2010;
struct edg{
int u,v,w;
}edge[5010];
vector<PII> g[N];
int n,m,c;
int dis[N][N];
int vis[N];
void solve()
{
cin >> n >> m >> c;
bool ok = true;
for(int i=1;i<=m;i++)
{
cin >> edge[i].u >> edge[i].v >> edge[i].w;
g[edge[i].u].push_back({edge[i].v,edge[i].w});
if(c>=edge[i].w) ok = false;
}
if(ok)
{
cout << 0 << endl;
return;
}
priority_queue<PII,vector<PII>,greater<PII>> path;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
dis[i][j] = inf;
}
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++) vis[j] = false;
while(path.size()) path.pop();
dis[i][i] = 0;
path.push({0,i});
while(path.size())
{
auto [len,u] = path.top();
path.pop();
if(vis[u]) continue;
vis[u] = true;
for(auto [v,w]:g[u])
{
if(dis[i][u]+w<dis[i][v])
{
dis[i][v] = dis[i][u]+w;
path.push({dis[i][u]+w,v});
}
}
}
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
if(i!=j&&dis[i][j] + dis[j][i]<=c)
{
cout << "2" << endl;
return;
}
}
}
cout << "1" << endl;
}
signed main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int T = 1;
//cin >> T;
while(T--) solve();
return 0;
}
D - Assumption is All You Need
我们从大往小考虑，每个数只能往后走，最优的一定是让区间最大值往前走（因为等下轮到区间最大值他就不能往前走了）。
#include <bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;
typedef pair<int,int> PII; typedef pair<double,double> PDD;
const int inf = 0x4f4f4f4f;
void solve()
{
int n;
cin >> n;
vector<int> a(n+1),b(n+1);
for(int i=1;i<=n;i++) cin >> a[i];
for(int i=1;i<=n;i++) cin >> b[i];
vector<PII> ans;
for(int i=n;i>=1;i--)
{
int l,r;
for(int j=1;j<=n;j++)
{
if(a[j]==i)
{
l = j;
break;
}
}
for(int j=1;j<=n;j++)
{
if(b[j]==i)
{
r = j;
break;
}
}
if(r<l)
{
cout << -1 << endl;
return;
}
while(l<r)
{
int mx = 0;
for(int j=l;j<=r;j++)
{
if(a[j]<i) mx = max(mx,a[j]);
}
for(int j=l;j<=r;j++)
{
if(a[j]==mx)
{
swap(a[l],a[j]);
ans.push_back({l,j});
swap(l,j);
break;
}
}
}
if(l<r)
{
swap(a[l],a[r]);
ans.push_back({l,r});
}
}
cout << ans.size() << endl;
for(auto [u,v]:ans) cout << u << " " << v << endl;
return;
}
signed main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int T = 1;
cin >> T;
while(T--) solve();
return 0;
}
B - A Plus B Problem
#include <bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;
typedef pair<int,int> PII; typedef pair<double,double> PDD;
const int inf = 0x4f4f4f4f;
void solve()
{
int n,q;
cin >> n >> q;
string s[2];
cin >> s[0] >> s[1];
vector bit(3,vector<int>(n+10,0));
for(int i=0;i<2;i++)
{
for(int j=0;j<n;j++)
{
bit[i][j+1] = s[i][j] - '0';
}
}
set<int> path;
for(int i=1;i<=n;i++)
if(bit[0][i]+bit[1][i]!=9) path.insert(i);
path.insert(0);path.insert(n+1);
while(q--)
{
int r,c,d;
cin >> r >> c >> d;
r--;
if(bit[0][c] + bit[1][c] != 9) path.erase(c);
int t = *path.lower_bound(c);
int len = 0,flag = 0;
int res = 0;
if(bit[r][c]!=d) res = 2;
if(bit[0][c] + bit[1][c] + (bit[0][t]+bit[1][t]>9)>9) flag=1;
bit[r][c] = d;
if(bit[0][c] + bit[1][c] + (bit[0][t]+bit[1][t]>9)>9) flag ^= 1;
//cout << "!t " << t << endl;
cout << (bit[0][c] + bit[1][c] + (bit[0][t]+bit[1][t]>9)) % 10 << " ";
if(flag) res += c-max(1ll,*(prev(path.lower_bound(c))));
cout << res << endl;
if(bit[0][c] + bit[1][c]!=9) path.insert(c);
}
}
signed main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int T = 1;
//cin >> T;
while(T--) solve();
return 0;
}