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;
}
else
del = 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;
}
