2022-9-29
前两道真的很水，然而我写挂了QAQ
T1
智力大冲浪
简单得不能再简单的贪心。先将每个游戏按扣钱为第一关键字降序，时刻为第二关键字升序排列。因为我们希望无法完成的游戏扣的钱更少。然后，从头到尾扫一遍，如果当前的游戏能被安排在它的最后时刻，就一定把它安排，这样对前面时间的影响才最少。如果不能，就再看该时刻前面的某一时刻有没有被安排。如果有就安排，没有的话这个游戏就只能被放弃，\(m\)就减去个它的代价。
代码
#include<bits/stdc++.h>
using namespace std;
int m,n,x,ok[510]={0};
struct game
{
int date,po,num;
}games[510];
bool cmp(game a,game b)
{
if(a.po!=b.po)return a.po>b.po;
return a.date<b.date;
}
int main()
{
scanf("%d%d",&m,&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&x);
games[i].date=x;
games[i].num=i;
}
for(int i=1;i<=n;i++)
{
scanf("%d",&x);
games[i].po=x;
}
sort(games+1,games+n+1,cmp);
for(int i=1;i<=n;i++)
{
int flag=0;
for(int j=games[i].date;j>=1;j--)
if(ok[j]==0){ok[j]=1;flag=1;break;}
if(flag==0)m-=games[i].po;
}
printf("%d",m);
return 0;
}
T2
[SHOI2013]发微博
同样一道水题。
暴力去模拟的复杂度是\(O(nm)\)的，发现是区间操作，考虑用类似前缀和的思路去优化。
用两个数组\(shou[i]\)和\(fa[i]\)表示第\(i\)个人目前收到的消息和发出的消息。那么每遇到一个“！ i”，就把\(i\)的\(fa++\)；遇到一个“+ i j”，就把\(shou[i]-=fa[j]\)，\(shou[j]-=fa[i]\)。为什么？因为在\(i\)、\(j\)建立联系之前他们所发的消息是不会被对方收到的，这里我们提前计算。每遇到一个“- i j”，就把\(shou[i]+=fa[j]\)，\(shou[j]+=fa[i]\)，即把当前的前缀和加上。这样我们就把一个“+”操作和与之对应的“-”操作处理了。
但这样会面临一个问题：一个“+”操作未必有对应的“-”操作，因为两个人加了好友之后可以一直不删。为了解决这个问题，我们可以倒着扫描（因为一个“-”操作一定有对应的“+”操作），同时上述操作反过来即可。
代码
#include<bits/stdc++.h>
#define MAXN 200010
#define MAXM 500010
using namespace std;
int n,m;
struct node
{
char op;
int a,b;
}no[MAXM];
int fa[MAXN],re[MAXN];
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
{
getchar();
no[i].op=getchar();
if(no[i].op=='!')scanf("%d",&no[i].a);
else scanf("%d%d",&no[i].a,&no[i].b);
}
for(int i=m;i>=1;i--)
{
if(no[i].op=='!')
fa[no[i].a]++;
else if(no[i].op=='+')
{
re[no[i].b]+=fa[no[i].a];
re[no[i].a]+=fa[no[i].b];
}
else if(no[i].op=='-')
{
re[no[i].b]-=fa[no[i].a];
re[no[i].a]-=fa[no[i].b];
}
}
for(int i=1;i<=n;i++)
printf("%d ",re[i]);
return 0;
}
T3
[SHOI2013]发牌
乍一看以为是约瑟夫问题，但\(R_i\)在变化，不好解决。观察题目后发现问题可以转换成每次把\(01\)序列的某个\(1\)变成\(0\)，并往后跳\(R_i\)个\(1\)这两个操作。可以用树状数组处理一个前缀和，每次往后跳的时候二分查找后面第\(R_i\)个\(1\)的位置并跳过去。
代码
#include<bits/stdc++.h>
#define MAXN 700010
using namespace std;
int n,r[MAXN],p=1,nowm;
int a[MAXN];
int nxt[MAXN],last[MAXN];
struct tree
{
int lowbit(int x)
{
return x&(-x);
}
void add(int num,int data)
{
for(int i=num;i<=MAXN-9;i+=lowbit(i))
{
a[i]+=data;
}
}
int getsum(int num)
{
int ans=0;
for(int i=num;i>0;i-=lowbit(i))
{
ans+=a[i];
}
return ans;
}
}tre;
int read()
{
int x=0,f=1;
char c=getchar();
while(c<'0'||c>'9')
{
if(c=='-')f=-1;
c=getchar();
}
while(c>='0'&&c<='9')
{
x=(x<<1)+(x<<3)+(c^48);
c=getchar();
}
return x*f;
}
bool check(int st,int ed,int step)
{
return tre.getsum(ed)-tre.getsum(st)<step;
}
int get_nxtk(int l,int r,int step)//在l到r的区间中，距开头为step的点的位置
{
while(l<r)
{
int mid=(l+r)>>1;
if(tre.getsum(mid)>=step)r=mid;
else l=mid+1;
}
return l;
}
int main()
{
n=read();
for(int i=1;i<=n;i++)
{
r[i]=read();
tre.add(i,1);
last[i]=i-1;
nxt[i]=i+1;
if(last[i]==0)last[i]=n;
if(last[i]==n+1)last[i]=1;
}
int cnt=n;
for(int i=1;i<=n;i++)
{
int step=r[i]%cnt+1;
int cha=tre.getsum(n)-tre.getsum(p-1);
if(cha<step)
{
p=get_nxtk(1,p-1,step-cha);
}
else
{
int pro=tre.getsum(p-1);
p=get_nxtk(p,n,pro+step);
}
printf("%d\n",p);
last[nxt[p]]=nxt[p];
nxt[last[p]]=last[p];
tre.add(p,-1);
cnt--;
p=nxt[p];
}
return 0;
}