李巨连续AK三场了，我跟南瓜打赌李巨连续AK七场，南瓜赌李巨连续AK五场。
DAY1
T1 qu
按题意拿stack,queue和priority_que模拟即可。特判没有元素却要取出的情况。
T2 ming
贪心发现ddl越小的任务越早完成越好，排序更新答案即可。
T3 zi
可能是昨天看了虚树我脑子不太好用，思维僵化的厉害，打算用虚树搞这道题，然后写了180+，连样例都懒得测知道根本过不了交了个暴力，结果暴力还有70。50min270pt+2h10min0pt。
实际上并不想需要虚树啊，我老想着怎么递推我tm就不能递归吗，递归然后记忆化只有那么好写了。
//Achen
#include<bits/stdc++.h>
#define For(i,a,b) for(int i=(a);i<=(b);i++)
#define Rep(i,a,b) for(int i=(a);i>=(b);i--)
#define Formylove return 0
const int N=,p=1e9+;
typedef long long LL;
typedef double db;
using namespace std;
int m;
LL T[N],sz[N],a[N],b[N],c[N],d[N],l[N]; template<typename T> void read(T &x) {
char ch=getchar(); x=; T f=;
while(ch!='-'&&(ch<''||ch>'')) ch=getchar();
if(ch=='-') f=-,ch=getchar();
for(;ch>=''&&ch<='';ch=getchar()) x=x*+ch-''; x*=f;
} #define pr pair<int,LL>
#define Pr pair<pr,LL>
#define MP make_pair
#define se second
#define fi first map<Pr,LL>D;
LL get_D(int i,LL x,LL y) {
if(x==y) return 0LL;
LL rs=;
if(x>y) swap(x,y);
if(D[MP(MP(i,x),y)]) return D[MP(MP(i,x),y)];
if(x<=sz[a[i]]&&y<=sz[a[i]]) rs=get_D(a[i],x,y);
else if(x>sz[a[i]]&&y>sz[a[i]]) rs=get_D(b[i],x-sz[a[i]],y-sz[a[i]]);
else rs=(get_D(a[i],x,c[i])+get_D(b[i],y-sz[a[i]],d[i])+l[i])%p;
D[MP(MP(i,x),y)]=rs; return rs;
} map<pr,LL>A;
LL get_A(int i,LL x) {
if(sz[i]==) return 0LL;
LL rs=;
if(A[MP(i,x)]) return A[MP(i,x)];
if(x<=sz[a[i]]) rs=(get_A(a[i],x)+get_A(b[i],d[i])+sz[b[i]]*(l[i]+get_D(a[i],c[i],x))%p)%p;
else rs=(get_A(b[i],x-sz[a[i]])+get_A(a[i],c[i])+sz[a[i]]*(l[i]+get_D(b[i],d[i],x-sz[a[i]]))%p)%p;
A[MP(i,x)]=rs; return rs;
} #define ANS
int main() {
#ifdef ANS
freopen("zi.in","r",stdin);
freopen("zi.out","w",stdout);
#endif
read(m);
sz[]=;
For(i,,m) {
read(a[i]); read(b[i]);
read(c[i]); read(d[i]);
c[i]+=; d[i]+=; read(l[i]);
sz[i]=sz[a[i]]+sz[b[i]];
T[i]=(T[a[i]]+T[b[i]]+sz[a[i]]*sz[b[i]]%p*l[i]%p+get_A(a[i],c[i])*sz[b[i]]%p+get_A(b[i],d[i])*sz[a[i]]%p)%p;
}
For(i,,m) printf("%lld\n",T[i]);
Formylove;
}
DAY2
T1 hao
这题数据出锅了吧，说好的一开始没有连着的实际上有而且不能被消去，这样实际上的消的效果就有多种可能了题意描述并不清楚。
一个坑点是读入字符串不能用scanf因为会有空串。
//Achen
#include<bits/stdc++.h>
#define For(i,a,b) for(int i=(a);i<=(b);i++)
#define Rep(i,a,b) for(int i=(a);i>=(b);i--)
#define Formylove return 0
const int N=4e3+;
typedef long long LL;
typedef double db;
using namespace std;
int n,head,pr[N],nxt[N],tot;
char a[N],s[N],o[]; template<typename T> void read(T &x) {
char ch=getchar(); x=; T f=;
while(ch!='-'&&(ch<''||ch>'')) ch=getchar();
if(ch=='-') f=-,ch=getchar();
for(;ch>=''&&ch<='';ch=getchar()) x=x*+ch-''; x*=f;
} void del(int x) {
int cnt=;
char bs=s[x];
if(pr[x]&&s[pr[x]]==bs) {
cnt++;
if(pr[pr[x]]&&s[pr[pr[x]]]==bs) cnt++;
}
if(nxt[x]&&s[nxt[x]]==bs) {
cnt++;
if(nxt[nxt[x]]&&s[nxt[nxt[x]]]==bs) cnt++;
}
if(cnt<) return ;
while(x&&s[x]==bs) {
if(x==head) {
pr[nxt[x]]=;
head=nxt[x];
x=nxt[x];
}
else {
if(nxt[x]) pr[nxt[x]]=pr[x];
nxt[pr[x]]=nxt[x];
if(s[pr[x]]==bs) x=pr[x];
else x=nxt[x];
}
}
if(x) del(x);
} void insert(int pos,char o,int f) {
int x=head,y=++tot;
s[y]=o;
if(!pos) {
nxt[y]=head;
if(head) pr[head]=y;
head=y;
}
else {
For(i,,pos-) x=nxt[x];
if(nxt[x]) {
pr[nxt[x]]=y;
nxt[y]=nxt[x];
}
nxt[x]=y; pr[y]=x;
}
if(f) del(y);
} void print(int x) {
if(!x) { puts(""); return; }
putchar(s[x]);
print(nxt[x]);
} int m=;
void scan() {
char ch=getchar();
for(;;) {
if(ch=='\n'||ch=='\r') break;
a[m++]=ch;
ch=getchar();
}
} #define ANS
int main() {
#ifdef ANS
freopen("hao.in","r",stdin);
freopen("hao.out","w",stdout);
#endif
scan();
For(i,,m-) insert(i,a[i],);
read(n);
For(cs,,n) {
int pos;
read(pos);
scanf("%s",o);
insert(pos,o[],);
if(!head) puts("-");
else print(head);
}
Formylove;
}
T2 kun
维护后缀最大值用栈贪心即可。好像学过栈的人都会吧。
T3 nan
考过的原题啊。发现答案是i*f[i]的前缀和，按f[i]分块地计算一下就好了。跟之前那题唯一的差别是多个询问所以要离线一起做。
//Achen
#include<bits/stdc++.h>
#define For(i,a,b) for(int i=(a);i<=(b);i++)
#define Rep(i,a,b) for(int i=(a);i>=(b);i--)
#define Formylove return 0
const int N=1e6,p=1e9+;
typedef long long LL;
typedef double db;
using namespace std;
int f[N+],T,n;
LL ans=; template<typename T> void read(T &x) {
char ch=getchar(); x=; T f=;
while(ch!='-'&&(ch<''||ch>'')) ch=getchar();
if(ch=='-') f=-,ch=getchar();
for(;ch>=''&&ch<='';ch=getchar()) x=x*+ch-''; x*=f;
} LL dc(LL a,LL b) {
if((a+b)%) return (b-a+)/%p*((a+b)%p)%p;
else return (a+b)/%p*((b-a+)%p)%p;
} struct qs {
int n,id;
friend bool operator <(const qs&A,const qs&B) {
return A.n<B.n;
}
}q[N];
LL rs[N]; #define ANS
int main() {
#ifdef ANS
freopen("nan.in","r",stdin);
freopen("nan.out","w",stdout);
#endif
f[]=; f[]=; f[]=;
int now=;
for(int i=;;i++) {
For(j,,f[i]) {
f[now+j]=i;
if(now+j==N) break;
}
now+=f[i];
if(now>=N) {
now=N; break;
}
}
read(T);
For(i,,T) {
read(q[i].n);
q[i].id=i;
}
sort(q+,q+T+);
int nq=; now=;
ans=;
for(int i=;;i++) {
while(nq<=T&&now+f[i]>=q[nq].n) {
rs[q[nq].id]=(ans+dc(now+,q[nq].n)*i%p)%p;
nq++;
}
if(nq>T) break;
ans=(ans+dc(now+,now+f[i])*i%p)%p;
now+=f[i];
}
For(i,,T) printf("%lld\n",rs[i]);
//cerr<<clock()<<endl;
Formylove;
}