2022ICPC济南站

K

Stack Sort

题意：给你一个长度为n的排列，设有m个栈，你需要将这n个数按出现顺序入栈，每次入栈操作从m个栈中选择一个栈从栈顶入栈。当所有元素入栈完成后，需要不断选择栈，将栈中元素弹空。需满足出栈顺序为1 2 3 ... n，问完成上述任务所需最少栈的个数为多少。

思路：遍历数组，设当前元素为x，我们就看是否存在栈顶为x+1的栈，若存在则入该栈；否则新开一个栈将x入栈。

#include <bits/stdc++.h>
#define ios ios::sync_with_stdio(0),cin.tie(0)
#define PII pair<int,int>
typedef long long ll;
const int N=1e6+10;
const int inf=0x3f3f3f3f;using namespace std;
/*
1 4 2 5 3
1 34 2 5 
找x+1存在否 存在不存在 ++
*/
int n;
bool st[N];
void solve()
{cin>>n;for(int i=1;i<=n+1;i++) st[i]=0;int ans=0;for(int i=1;i<=n;i++){int x;cin>>x;if(st[x+1]){st[x+1]=0;st[x]=1;}else{st[x]=1;ans++;}}cout<<ans<<'\n';
}
signed main()
{//freopen("input.txt","r",stdin);//freopen("output.txt","w",stdout);ios;int _t=1;cin>>_t;while(_t--) solve();system("pause");return 0;
}

M

Best Carry Player

题意：给定n个元素的数组a[]，起始sum=0，不断执行sum+=a[i]，问加法过程中的总进位次数为多少？

思路：模拟

#include <bits/stdc++.h>
#define ios ios::sync_with_stdio(0), cin.tie(0)
#define PII pair<int, int>
typedef long long ll;
const int N = 1e5 + 10;
const int inf = 0x3f3f3f3f;using namespace std;
int n;
string a[N];
void solve()
{cin >> n;for (int i = 1; i <= n; i++){string x;cin >> x;reverse(x.begin(), x.end());a[i] = x;}string ret = "000000000000000";int ans = 0;int del = 0;for (int i = 1; i <= n; i++){for (int j = 0; j < 15; j++){int c1 = int(ret[j] - '0');int c2 = 0;if(j<a[i].size()) c2=int(a[i][j] - '0');int t = c1 + c2 + del;ret[j] = char(t % 10 + '0');if (t >= 10){ans++;del = 1;}elsedel = 0;}}cout << ans << '\n';
}
signed main()
{// freopen("input.txt","r",stdin);// freopen("output.txt","w",stdout);ios;int _t = 1;cin >> _t;while (_t--)solve();system("pause");return 0;
}

E

Identical Parity

题意：一个序列的值定义为所有数字的和，给定n，k问是否存在长度为n的排列满足所有长度为k的子段的值奇偶性都相同。

思路：当k=1时，若n=1 Yes；k=1, n不为1 No

当k为偶数时，我们可以奇偶交替的放，Yes

当k为奇数时，我们可以分成k组，每组的下标满足a, a+k, a+2k...a属于[1,k]，同一组我们放相同奇偶的数。我们发现这样的序列就满足条件。

设n/k=b余c，我们将k/2个组，这些组的位置放偶数；其余k/2+1个组，这些组的位置上放奇数。那么还剩下c个数没放，判断剩下的数是否满足奇偶个数。

#include <bits/stdc++.h>
#define ios ios::sync_with_stdio(0),cin.tie(0)
#define PII pair<int,int>
#define int long long
typedef long long ll;
const int N=1e6+10;
const int inf=0x3f3f3f3f;using namespace std;
int n,k;
void solve()
{cin>>n>>k;if(k==1){if(n==1) cout<<"Yes\n";else cout<<"No\n";}else if(k%2==0) cout<<"Yes\n";else{int tot_o=n/2,tot_j=(n+1)/2;//总的奇偶个数int k_o=k/2,k_j=k/2+1;//k组中有多少组奇数偶数int b=n/k,c=n%k;int r_o=tot_o-b*k_o,r_j=tot_j-b*k_j;//放完k组，还剩多少奇偶数没放if(r_o>=0&&r_j>=0&&r_o+r_j==c){if(r_o<=k_o&&r_j<=k_j) cout<<"Yes\n";else cout<<"No\n";}else cout<<"No\n";}
}
signed main()
{//freopen("input.txt","r",stdin);//freopen("output.txt","w",stdout);ios;int _t=1;cin>>_t;while(_t--) solve();system("pause");return 0;
}

A

Tower

题意：有n座不同高度的塔，第i座塔的高度为a[i]

你可以将其中的m座塔移除，然后进行下面的操作：

1.选择一座塔，将其高度 a[i]增加 1

2.选择一座塔，将其高度 a[i]减少 1

3.选择一座塔，将其高度 a[i]/=2，向下取整

不允许操作后塔的高度为0。问将剩余n-m座塔的高度搞成相同所需最少的操作次数。

思路：最后变成的相同高度一定是某个塔的高度不断/2的结果。所以我们可以通过枚举最后高度，来计算塔到这个高度的最小操作次数。

#include <bits/stdc++.h>
#define ios ios::sync_with_stdio(0),cin.tie(0)
#define PII pair<int,int>
#define int long long
typedef long long ll;
const int N=1e6+10;
const int inf=0x3f3f3f3f;using namespace std;
int n,m;
int a[N];
int get(int now,int x)
{int ret=0;if(now<x) ret=x-now;else if(now==x) ret=0;else{while(now>x){if(now>x&&now/2<=x){ret+=min(now-x,1+x-now/2);break;}now/=2;ret++;}}return ret;
}
void solve()
{cin>>n>>m;for(int i=1;i<=n;i++)cin>>a[i];set<int>s;for(int i=1;i<=n;i++){int x=a[i];s.insert(x);while(x>=2){x/=2;s.insert(x);}}int ans=1e18;for(auto x:s){vector<int>v;for(int i=1;i<=n;i++){int t=get(a[i],x);v.push_back(t);}sort(v.begin(),v.end());int tem=0;for(int i=0;i<n-m;i++)tem+=v[i];ans=min(ans,tem);}cout<<ans<<'\n';
}
signed main()
{//freopen("input.txt","r",stdin);//freopen("output.txt","w",stdout);ios;int _t=1;cin>>_t;while(_t--) solve();system("pause");return 0;
}

D

Frozen Scoreboard

题意：给你封榜前的情况和最终通过的题数和罚时，问最终的榜单

思路：将封榜前的过题数和罚时减去，再对封榜后的题进行二进制枚举，判断合法

#include <bits/stdc++.h>
#define ios ios::sync_with_stdio(0),cin.tie(0)
#define PII pair<int,int>
#define int long long
typedef long long ll;
const int N=1e6+10;
const int inf=0x3f3f3f3f;using namespace std;
int n,m;
int a[N],b[N];
struct node{char op;int x,y;int num;
}P[N];
void solve()
{cin>>n>>m;for(int i=1;i<=n;i++){cin>>a[i]>>b[i];int nowt=0,nowcnt=0;vector<node>uk;for(int i=0;i<m;i++){char op;cin>>op;if(op=='+'){int u,v;char _;cin>>u>>_>>v;nowcnt++;nowt+=(u-1)*20+v;P[i]={'+',u,v};}else if(op=='-') {int u;cin>>u;P[i]={'-',u};}else if(op=='?'){int u,v;cin>>u>>v;P[i]={'?',u,v,i};uk.push_back({'?',u,v,i});}else P[i]={'.'};}if(nowcnt==a[i]&&nowt==b[i]){cout<<"Yes\n";for(int j=0;j<m;j++){if(P[j].op=='+') printf("+ %d/%d\n",P[j].x,P[j].y);else if(P[j].op=='-') printf("- %d\n",P[j].x);else if(P[j].op=='?') printf("- %d\n",P[j].y);else printf(".\n");}}else if(nowcnt<a[i]&&nowt<b[i]){int cnt=a[i]-nowcnt;int t=b[i]-nowt;bool f=0;for(int j=0;j<(1<<uk.size());j++){int mi=0,ma=0;for(int k=0;k<uk.size();k++){if((j>>k)&1){mi+=240+(uk[k].y-uk[k].x)*20;ma+=299+(uk[k].y-1)*20;}}if(t>=mi&&t<=ma){map<int,node>ans;int remt=t-mi;int finish=0;for(int k=0;k<uk.size();k++){if((j>>k)&1){int num=uk[k].num;int cishu=min(remt/20,uk[k].x-1);//封榜后wa了多少次ans[num].x=(uk[k].y-uk[k].x+cishu+1);remt-=cishu*20;int r1=min(remt,59ll);remt-=r1;ans[num].y=240+r1;finish++;}}if(remt==0&&finish==cnt){f=1;cout<<"Yes\n";for(int k=0;k<m;k++){if(P[k].op=='+') printf("+ %d/%d\n",P[k].x,P[k].y);else if(P[k].op=='-') printf("- %d\n",P[k].x);else if(P[k].op=='?'&&ans[k].x) printf("+ %d/%d\n",ans[k].x,ans[k].y);else if(P[k].op=='?') printf("- %d\n",P[k].y);else printf(".\n");}break;}}}if(!f) cout<<"No\n";}else cout<<"No\n";}
}
signed main()
{//freopen("input.txt","r",stdin);//freopen("output.txt","w",stdout);//ios;int _t=1;//cin>>_t;while(_t--) solve();system("pause");return 0;
}