2022年浙大城市学院新生程序设计竞赛（同步赛）（补题）
A：OP
签到题
#include <bits/stdc++.h>
using namespace std;
int main ()
{
cout<<"fengqibisheng, yingyueerlai!";
return 0;
}
B:Steel of Heart
#include <bits/stdc++.h>
using namespace std;
#define int long long
int now,h;
int t,m;
map<int,int>tt;
signed main ()
{
cin>>now>>h>>m;
bool yes=false;
while (m--)
{
int x,y;
char ch;
int op,opt;
cin>>x>>ch>>y>>op;
t=x*60+y;
//cout<<t<<'\n';
if (op==1)
{
now+=800;
yes=true;
}
else if (op==2)
{
now+=h;
}
else
{
cin>>opt;
if (yes)
{
if (!tt[opt])
{
now+=(125+now*6/100)/10;
tt[opt]=t;
}
else
{
if ((t-tt[opt])>=30)//注意这个一定要包括=，我之前就是没有等于号就错了
{
now+=(125+now*6/100)/10;
tt[opt]=t;
}
}
}
}
}
cout<<now;
}
C:Add 9 Zeros
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=5e5+10;
int n,a[maxn];
set<int>st;
signed main ()
{
cin>>n;
for (int i=1;i<=n;i++)
{
cin>>a[i];
st.insert(a[i]);
st.insert(a[i]+9);
}
int ans=st.size()-n;
cout<<ans<<'\n';
return 0;
}
F:Survior
题意大致是i初始价值为a[i],每分钟都会减少b[i]价值，而我们可以在任意时间给第i个人补充价值，使得i存活下来(最后的价值>0),但是最多补充的次数不超过k次，并且不存活了后就一定不可以再补充价值了，只要坚持到第m分钟就结束了
思路：我们可以直接求出这m分钟总共会消耗多少能量，计算每次补充c[i]能量使得i坚持到第m分钟，最后把cnt按从小到大的顺序排列下来，优先选择补充能量次数少的（毕竟次数有限），只要次数可以够，就可以让i坚持下来,ans++,最后输出答案
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=2e5+10;
int n,m,k,a[maxn],b[maxn],c[maxn];
int cnt[maxn];
signed main ()
{
cin>>n>>m>>k;
for (int i=1;i<=n;i++)
{
cin>>a[i];
}
for (int i=1;i<=n;i++)
{
cin>>b[i];
}
for (int i=1;i<=n;i++)
{
cin>>c[i];
a[i]-=m*b[i];
if (a[i]>0) cnt[i]=0;
else
{
cnt[i]=-1*a[i]/c[i]+1;
}
}
sort(cnt+1,cnt+1+n);
int ans=0;
for (int i=1;i<=n;i++)
{
if (cnt[i]<0) continue;
if (k>=cnt[i])
{
k-=cnt[i];
ans++;
}
else break;
}
cout<<ans;
return 0;
}
G：Red Black Tree
#include <bits/stdc++.h>
using namespace std;
const int maxn=1e6+10;
#define int long long //记得一定要开long long
struct node
{
int l,r;
//l是表示这片叶子在这一行的第i个，r是这片叶子一定会形成的一个三角形的最大可达的列
}a[maxn];
bool cmp(node x,node y)//按照三角形的形成规律，l是三角形的左边边界，r是三角形的右边边界
{
return x.l<y.l;//l从小到大排序，判断是否有出现三角形可以合成的情况
}
int n,k;
signed main ()
{
cin>>n>>k;
for (int i=1;i<=k;i++)
{
int x,y;
cin>>x>>y;
a[i].l=y;
a[i].r=y-x+n;
}
sort(a+1,a+1+k,cmp);
int l=a[1].l,r=a[1].r;
int ans=0;
for (int i=2;i<=k;i++)
{
int tl=a[i].l;
int tr=a[i].r;
if (tl<=r+1)//tl<=r是第一种情况，tl==r+1是第二种情况(如图所示)
{
r=max(r,tr);
}
else
//这个时候，三角形不可能合成，那么它后面的也一定不可以合成，那么就把这个三角形里面的叶子数量求出
{
ans+=(r-l+1+1)*(r-l+1)/2;
l=a[i].l,r=a[i].r;
}
}
ans+=(r-l+1+1)*(r-l+1)/2;
cout<<ans<<'\n';
}
I：Digit Problem
#include <bits/stdc++.h>
using namespace std;
const int maxn=1e6+10;//因为最长是a+b-1所以要开1e6+10
int a,b,c;
bool visx[maxn],visy[maxn];//分别代表x，y每一位上01的分布情况
int main ()
{
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);//加上这个不会运行超时
cin>>a>>b>>c;
if (a==0&&c!=0)
{
cout<<-1;
return 0;
}
if ((a+b-1)<c)
{
cout<<-1;
return 0;
}
if (a==0&&c==0)
{
for (int i=0;i<=a+b-1;i++)
{
cout<<0;
}
cout<<'\n';
for (int i=0;i<=a+b-1;i++)
{
cout<<0;
}
return 0;
}
visx[c]=true;
visy[0]=true;
int k=a-1;
for (int i=0;i<=a+b-1&&k>0;i++)
{
if (i!=0&&i!=c)//这两个位置已经安排好了
{
visx[i]=visy[i]=true;
k--;//千万不要直接拿a来减，后面还有a会用到
}
}
if (k)//凑不齐a个1
{
cout<<-1;
return 0;
}
for (int i=a+b-1;i>=0;i--)
{
if (visx[i]) cout<<1;
else cout<<0;
}
cout<<'\n';
for (int i=a+b-1;i>=0;i--)
{
if (visy[i]) cout<<1;
else cout<<0;
}
return 0;
}
J：Simple Game
奇数=奇数+偶数
偶数=奇数+奇数，偶数=奇数+奇数
所以，如果和为奇数，他两的差一定是奇数（奇数-偶数=奇数），否则就是偶数
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=1e6+10;
int n,a[maxn];
signed main ()
{
cin>>n;
int sum=0;
for (int i=1;i<=n;i++)
{
cin>>a[i];
sum+=a[i];
}
if (sum&1)
{
cout<<"Alice\n";
}
else
{
cout<<"Bob\n";
}
//cout<<"*";
return 0;
}
K：Bit
#include <bits/stdc++.h>
using namespace std;
const int maxn=2e5+10;
#define int long long
int n,q,f0=0,f1=0x7fffffff;//fo代表取0时y的值，一开始全是0，f1代表,取1时y的值，一开始有31个1
signed main ()
{
cin>>n>>q;
while (n--)
{
int op,a;
cin>>op>>a;
if (op==1)
{
f0=f0&a;
f1=f1&a;
}
else if (op==2)
{
f0=f0|a;
f1=f1|a;
}
else if (op==3)
{
f0=f0^a;
f1=f1^a;
}
}
while (q--)
{
int r;
cin>>r;
int p=log2(r);//r二进制形式上第一个1，因为r是最大的，这一定是最高位
int ans=0;
for (int i=(1<<p);i;i>>=1)//i代表的是二进制每一位的权值取1时的大小，
{//可类比二进制转化成十进制的过程,取和不取分别代表着二进制上这一位是0是1
//两个条件（取1）
//1，ans存从最高位到第log2(i)位前已经取值的十进制数,
//第log2(i）位也取1的情况下的数，ans+i，但是这一个个数必须要小于r（r是最大值）
//2，log2(i)位取1时必须要比取0的情况下得到的数大，题目要求y最大化,
if((ans+i)<=r&&((f1&i)>(f0&i))) ans+=i;
}
cout<<ans<<'\n';
}
}
L :Elden Ring
#include <bits/stdc++.h>
using namespace std;
int n,m,k;
int ans[2000+10];
int main ()
{
cin>>n>>m>>k;
int now=1,x=1,y=n+1;
for (int i=1;i<=n+n;i++)
{
ans[i]=i;
}
if (k<m)
{
for (int i=1;i<=n+n;i++)
{
cout<<ans[i]<<" ";
}
return 0;
}
int p=m;
p=p%n;
//cout<<p<<" "<<m<<" "<<m<<" ";
int id=p;
if (p==0) id=n;
// cout<<id<<'\n';
swap(ans[id],ans[n+id]);
now=m;
while ((now+m)<=k)
{
now+=m;
p=(p+m)%n;
id=p;
if (p==0) id=n;
//cout<<id<<'\n';
swap(ans[id],ans[id+n]);
}
for (int i=1;i<=n+n;i++)
{
cout<<ans[i]<<" ";
}
return 0;
}