20220929(中)
t1 智力大冲浪
思路
非常明显的贪心，能尽可能的少扣钱就少扣钱，即将每个游戏按其价值从大到小排序。那么考虑如何在该基础上加入时间的情况下贪心。其实也很显然，能在自身规定时间踩点完成是最好的。因为这样能最大程度地避免影响其它游戏。如果该时间已经被使用过了，就往之前的找没有使用过的时间即可。毕竟如果两个游戏冲突，按照贪心的思想，肯定得优先保证价值更大的。
点击查看代码
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#define ll long long
#define fo(i,x,y) for(int i=x;i<=y;++i)
using namespace std;
template<typename T>inline void in(T &x){
x=0;int f=0;char c=getchar();
for(;!isdigit(c);c=getchar())f|=(c=='-');
for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+(c^48);
x=f?-x:x;
}
template<typename T>inline void out(T x){
if(x<0)x=~x+1,putchar('-');
if(x>9)out(x/10);
putchar(x%10^48);
}
const int N=505;
int n;
ll m;
int t[N],w[N];
struct game{
ll t,w;
}g[N];
bool v[N];
inline bool cmp(game a,game b){
return a.w>b.w;
}
int main(){
in(m),in(n);
fo(i,1,n)in(g[i].t);
fo(i,1,n)in(g[i].w);
sort(g+1,g+n+1,cmp);
fo(i,1,n){
if(!v[g[i].t]){
v[g[i].t]=1;
}
else{
int j;
for(j=g[i].t-1;v[j]&&j;--j);
if(j)v[j]=1;
elsem-=g[i].w;
}
}
out(m);
return 0;
}
小优化
一个可以将该算法从\(O(n^{2})\)优化成\(O(n)\)的小优化。可以发现，我们处理一个游戏时，会往回扫之前已经用过的时间。我们可以考虑在用完该时间后将该时间与前面的时间合并，使得每次只需往回扫一次即可。
t2 发微博
暴力思路
首先，我们可以暴力地进行模拟，\(x\)发微博时给其所有好友答案加1，成为好友时加入，解除好友时删除，可以用vector或者set实现。不过vector删除操作比较慢，而且还需要迭代器，但是set插入操作又不如vector。
点击查看代码
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<vector>
#define ll long long
#define fo(i,x,y) for(int i=x;i<=y;++i)
using namespace std;
template<typename T>inline void in(T &x){
x=0;int f=0;char c=getchar();
for(;!isdigit(c);c=getchar())f|=(c=='-');
for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+(c^48);
x=f?-x:x;
}
template<typename T>inline void out(T x){
if(x<0)x=~x+1,putchar('-');
if(x>9)out(x/10);
putchar(x%10^48);
}
const int N=200005;
int m,n,x,y;
char c;
vector <int> p[N];
vector <int> ::iterator it;
int ans[N];
int main(){
in(n),in(m);
fo(i,1,m){
scanf("%c",&c);
if(c=='!'){
in(x);
if(p[x].size())fo(i,0,p[x].size()-1)++ans[p[x][i]];
}
else if(c=='+'){
in(x),in(y);
p[x].push_back(y);
p[y].push_back(x);
}
else{
in(x),in(y);
it=find(p[x].begin(),p[x].end(),y);
if(it!=p[x].end())p[x].erase(it);
it=find(p[y].begin(),p[y].end(),x);
if(it!=p[x].end())p[y].erase(it);
}
}
fo(i,1,n-1)out(ans[i]),putchar(' ');
out(ans[n]);
return 0;
}
暴力做法遇到\(x\)多次发微博，且\(x\)好友很多时，就非常容易\(tle\)，最坏情况的时间复杂度大概是\(O(nm)\)的，所以需要进行优化。
优化思路
插入操作显然是无法进行什么优化的咯，所以就考虑如何优化统计答案的过程。可以发现，一个人\(x\)贡献的答案其实就是\(x\)的好友\(y\)在\(x\)和\(y\)成为好友后到解除好友之前，\(y\)所发出的微博数。那我们就可以用一个类似于前缀和的方式维护它。在\(x,y\)成为好友时给\(x,y\)的答案个数减去他们之前所发微博数，解除好友后加上总微博数，其实就是完成了一个类似于\(sum[r]-sum[l-i]\)前缀和的操作。不过，还要注意最后可能还有好友关系没有解除，需要手动解除一下。
点击查看代码
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<vector>
#define ll long long
#define fo(i,x,y) for(int i=x;i<=y;++i)
using namespace std;
template<typename T>inline void in(T &x){
x=0;int f=0;char c=getchar();
for(;!isdigit(c);c=getchar())f|=(c=='-');
for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+(c^48);
x=f?-x:x;
}
template<typename T>inline void out(T x){
if(x<0)x=~x+1,putchar('-');
if(x>9)out(x/10);
putchar(x%10^48);
}
const int N=200005;
int m,n,x,y;
char c;
int cnt[N];
vector <int> p[N];
vector <int> ::iterator it;
int ans[N];
int main(){
in(n),in(m);
fo(i,1,m){
scanf("%c",&c);
if(c=='!'){
in(x);
++cnt[x];
}
else if(c=='+'){
in(x),in(y);
ans[x]-=cnt[y];
ans[y]-=cnt[x];
p[x].push_back(y);
p[y].push_back(x);
}
else{
in(x),in(y);
ans[x]+=cnt[y];
ans[y]+=cnt[x];
it=find(p[x].begin(),p[x].end(),y);
if(it!=p[x].end())p[x].erase(it);
it=find(p[y].begin(),p[y].end(),x);
if(it!=p[x].end())p[y].erase(it);
}
}
fo(i,1,n)
for(it=p[i].begin();it!=p[i].end();++it)ans[i]+=cnt[*it];
fo(i,1,n-1)out(ans[i]),putchar(' ');
out(ans[n]);
return 0;
}
t3 发牌
朴素算法
模拟。。。就不用多说了吧。
优化思路
如果能在让一次销牌在处理时直接跳过已经发出的牌，可以省下大把时间。
一.我最初是想将已经发出的牌排到外面，即将一个序列\(1,2,3,4\)，发出牌\(3\)，变为\(1,2,3\)，最后将大于等于3的位置在查找时加上这个位置排出的数的个数，将其复原为原序号。
二.貌似用链表也能实现这个操作，不过查找还是比较慢。
三.可以发现其实这道题就是在求牌堆顶之后排名第\(r[i]\)的数，这显然可以用平衡树维护，比如防火墙，树状数组其实也可以维护，只不过在查找时需要二分。
简单de算法
浅谈一下简单且比较好理解的算法: 权值线段树。(我还是太蒻了，同机房dalao一眼就看出来了
这里推一波dalao的博客oWXDo
我们用权值线段树来维护排名，这个排名是指从牌堆顶到一张牌的个数。这样应该就不用多讲了，毕竟这道题就相当于权值线段树的板子，看下注解就明白了。
点击查看代码
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#define ll long long
#define fo(i,x,y) for(int i=x;i<=y;++i)
using namespace std;
template<typename T>inline void in(T &x){
x=0;int f=0;char c=getchar();
for(;!isdigit(c);c=getchar())f|=(c=='-');
for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+(c^48);
x=f?-x:x;
}
template<typename T>inline void out(T x){
if(x<0)x=~x+1,putchar('-');
if(x>9)out(x/10);
putchar(x%10^48);
}
const int N=700005;
int n;
int r;
struct node{
int lch,rch,l,r,val;
}rt[N<<2];
int tot;
int build(int l,int r){
int x=++tot;
rt[x].l=l;
rt[x].r=r;
if(l==r){
rt[x].val=1;
return x;
}
int mid=l+r>>1;
rt[x].lch=build(l,mid);
rt[x].rch=build(mid+1,r);
rt[x].val=rt[rt[x].lch].val+rt[rt[x].rch].val;
return x;
}
int query(int x,int pos){
--rt[x].val;
if(rt[x].l==rt[x].r){
return rt[x].l;
}
if(pos<=rt[rt[x].lch].val)return query(rt[x].lch,pos);
else return query(rt[x].rch,pos-rt[rt[x].lch].val);
}
int now;//记录将几张牌放到牌库底
int main(){
in(n);
build(1,n);
for(int i=n;i>=1;--i){
in(r);
now+=r;
now%=i;//防止now的值大于权值线段树总值
out(query(1,now+1)),putchar('\n');//查找将now张牌放到牌库底后牌库顶的牌是哪张
}
return 0;
}