CSP-S2020
儒略日
模拟
分几段来做：
- 公元前
- 1582年前
- 1582年
- 1600年及以前
- 1600年后
每次确定到哪四年就可以了，四年之内暴力每一月。
时间复杂度 (O(48n))。
#include<bits/stdc++.h>
using namespace std;
#define int long long
inline int read(){
int x=0,f=1,c=getchar();
while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
return f==1?x:-x;
}
const int year=365,bc=1721424,bd1=577460;
int mon[13]={0,31,28,31,30,31,30,31,31,30,31,30,31},ren[5],T;
inline void chu(int n,int mod,int &x,int &y){
x=n/mod;
y=n%mod;
if(!y){x--;y=mod;}
}
inline void getdata(int day,int &n,int &y,int &r){
for(int t=1,nw;t<=4;t++){
for(int i=1;i<=12;i++){
nw=mon[i];
if(i==2)nw+=ren[t];
if(day>nw)day-=nw;
else{
n+=t;
y=i;
r=day;
return;
}
}
}
}
inline void solve(){
static int x,y,u,v,fl,n;
memset(ren,0,sizeof(ren));
T++;
fl=0;
n=read()+1;
if(n<=bc){
chu(n,year*4+1,x,y);
ren[1]=1;
x*=4;
getdata(y,x,u,v);
cout<<v<<" "<<u<<" "<<4713-x+1<<" BC
";
return;
}
n-=bc;
if(n<=bd1){
chu(n,year*4+1,x,y);
ren[4]=1;
x=x*4;
getdata(y,x,u,v);
cout<<v<<" "<<u<<" "<<x<<"
";
return;
}
n-=bd1;
if(n<=year-10){
mon[10]-=10;
x=0;
getdata(n,x,u,v);
mon[10]+=10;
if(u==10&&v>4)v+=10;
cout<<v<<" "<<u<<" 1582
";
return;
}
n-=year-10;
if(n<=year*18+5){
chu(n,year*4+1,x,y);
ren[2]=1;
x=x*4;
getdata(y,x,u,v);
cout<<v<<" "<<u<<" "<<x+1582<<"
";
return;
}
n-=(year*18+5);
chu(n,year*400+97,x,y);
x=x*400;
if(y<=year*100+24);
else if(y<=(year*100+24)*2){x+=100;y-=(year*100+24);}
else if(y<=(year*100+24)*3){x+=200;y-=(year*100+24)*2;}
else{x+=300;y-=(year*100+24)*3;fl=1;}
chu(y,year*4+1,u,v);
y=v;
x+=u*4;
if(u<24||fl)ren[4]=1;
getdata(y,x,u,v);
cout<<v<<" "<<u<<" "<<x+1600<<"
";
}
signed main(){
for(int Q=read();Q--;)solve();
return (0-0);
}
动物园
位运算 签到题
已有的位数加上可以不用饲料的位数即为总的可以养的动物数。
注意特判 n=m=0,k=64 时答案是 (2^{64}) 会爆 long long。
时间复杂度 (O(n+m+k))。
#include<bits/stdc++.h>
using namespace std;
inline int read(){
int x=0,f=1,c=getchar();
while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
return f==1?x:-x;
}
#define ul unsigned long long
inline ul readul(){
ul x=0;int c=getchar();
while(!isdigit(c))c=getchar();
while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
return x;
}
ul hav;
int n,m,c,k,zhong,deg[100];
int main(){
// freopen("zoo.in","r",stdin);
// freopen("zoo.out","w",stdout);
n=read();m=read();c=read();k=read();
if(!n&&!m&&k==64){puts("18446744073709551616");return (0-0);}
for(int i=1;i<=n;i++)hav|=readul();
for(int i=1,x;i<=m;i++){
deg[read()]++;
x=read();
}
for(int i=0;i<k;i++)if(!deg[i])hav|=((ul)1<<i);
for(int i=0;i<k;i++)if((hav>>i)&1)zhong++;
if(zhong<64)hav=((ul)1<<zhong);
else hav=0;
cout<<hav-n<<"
";
return (0-0);
}
函数调用
拓扑排序 动态规划
考虑只有乘号直接拓扑排序后 DP，只有加号反拓扑序 DP，每个点经历了几次。
然后结合的话会有顺序问题，我们先 DP 一次只有乘号，然后反着DP 加号时，要乘上后缀积即可。
时间复杂度 (O(n+m))。
#include<bits/stdc++.h>
using namespace std;
inline int read(){
int x=0,f=1,c=getchar();
while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
return f==1?x:-x;
}
#define ll long long
const int mod=998244353;
inline int fix(int x){
return x+((x>>31)&mod);
}
inline int add(int x,int y){
return fix(x+y-mod);
}
inline int dec(int x,int y){
return fix(x-y);
}
inline int mul(int x,int y){
return (ll)x*y%mod;
}
inline void ADD(int &x,int y){
x=fix(x+y-mod);
}
inline void DEC(int &x,int y){
x=fix(x-y);
}
inline void MUL(int &x,int y){
x=(ll)x*y%mod;
}
const int M=1100004;
struct edge{
int v,nxt;
}e[M];
int first[M],deg[M],cnt;
inline void addedge(int u,int v){
e[++cnt].v=v;e[cnt].nxt=first[u];first[u]=cnt;
deg[v]++;
}
queue<int>q;
int n,m,Q,a[M],dfn[M],f[M],ml[M],ans[M],op[M],xx[M],vv[M];
inline void tuopu(){
for(int i=m;i;i--)if(!deg[i])q.push(i);
while(!q.empty()){
int x=q.front();q.pop();
dfn[++dfn[0]]=x;
for(int i=first[x],v;i;i=e[i].nxt){
v=e[i].v;
deg[v]--;
if(!deg[v])q.push(v);
}
}
}
inline void solve1(){
for(int t=m,x;t;t--){
x=dfn[t];
assert(x);
if(op[x]==2){
ml[x]=vv[x];
}
else ml[x]=1;
for(int i=first[x],v;i;i=e[i].nxt){
v=e[i].v;
MUL(ml[x],ml[v]);
}
}
}
inline void solve2(){
f[dfn[1]]=1;
for(int t=1,x,tmp;t<=m;t++){
x=dfn[t];
if(op[x]==1){
ADD(ans[xx[x]],mul(vv[x],f[x]));
}
tmp=f[x];
for(int i=first[x],v;i;i=e[i].nxt){
v=e[i].v;
ADD(f[v],tmp);
MUL(tmp,ml[v]);
}
}
}
int main(){
// freopen("call.in","r",stdin);
// freopen("call.out","w",stdout);
n=read();
for(int i=1;i<=n;i++){
a[i]=read();
}
m=read();
for(int i=1,k;i<=m;i++){
op[i]=read();
if(op[i]==1){
xx[i]=read();vv[i]=read();
}
else if(op[i]==2){
vv[i]=read();
}
else{
k=read();
for(int j=1;j<=k;j++)addedge(i,read());
}
}
Q=read();
++m;
for(int i=1;i<=Q;i++)addedge(m,read());
tuopu();
solve1();
solve2();
for(int i=1;i<=n;i++)ADD(ans[i],mul(a[i],ml[m]));
for(int i=1;i<=n;i++)cout<<ans[i]<<" ";
return (0-0);
}
贪吃蛇
贪心 博弈 单调性 奇偶性
先讲讲暴力 (O(nlog n)) 吧
我的暴力：
求出每个点的 las 最后杀蛇的时刻（时刻从 n 到 1），ded 每只蛇死的的时刻。然后按 las 从小到大排序，若一个蛇的区间内有蛇是肯定不会杀别人的，这只蛇就可以杀，用前缀和维护一下不敢杀的蛇。对所有不敢杀的蛇的 las 取 max 即是答案。
同学的暴力：
对每个时刻维护一个最近的不敢吃的时刻，上一个时刻要么继承这个时刻要么自己不吃。
正解 (O(n))
结论一：若一个时刻 a 吃了 b，a 不会变成最小的那么久可以吃。
下一个时刻
c吃d，显然有 (c-d<a-b)，那么c不会被吃a就不会被吃。
结论二：若一个时刻 a 吃了 b 后变成的最小的，那么往下最多只有一轮就结束了。
若有两轮那么
a就被吃掉了。
结论三：每次新产生的会单调递减，但在变成最小后经过一段时间后又不是最小的就会被破坏（值相同时标号会产生这种情况）。
不是最小时显然是单调的，是最小时下一轮
c吃a-b，(c-a+bleq c) 还是最小的。
于是先模拟到不是最小的轮数 (res)，k 轮后又变成了最小的（用两个队列维护一下），再往下一定最大的就直接吃掉最小的了所以不可能在往下推了。那么 (ans=res-((k&1)xor 1))，(k=1) 是显然继续的轮数是 0，(k=2) 时显然是 1，以后可以用类似 SG 函数的推法推出刚才的结论。要特判一下一直到最后都有单调性的情况。
//starusc
#include<bits/stdc++.h>
using namespace std;
inline int read(){
int x=0,f=1,c=getchar();
while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
return f==1?x:-x;
}
const int N=1e6+4;
int n,A[N];
namespace que{
int h1,h2,t1,t2;
pair<int,int>q1[N],q2[N];
inline void build(){
for(int i=1;i<=n;i++)q1[n-i+1]=make_pair(A[i],i);
h1=1;t1=n;
h2=1;t2=0;
}
inline pair<int,int> getmx(){
if(h2>t2||(h1<=t1&&q1[h1]>q2[h2]))return q1[h1++];
return q2[h2++];
}
inline pair<int,int> getmn(){
if(h2>t2||(h1<=t1&&q1[t1]<q2[t2]))return q1[t1--];
return q2[t2--];
}
inline pair<int,int> mnval(){
if(h2>t2||(h1<=t1&&q1[t1]<q2[t2]))return q1[t1];
return q2[t2];
}
inline bool dec(){
pair<int,int>mx=getmx(),mn=getmn(),nw=make_pair(mx.first-mn.first,mx.second),tmp;
if(h1<=t1||h2<=t2)tmp=mnval();
q2[++t2]=nw;
return (h1>t1&&h2>t2)||nw<tmp;
}
}
inline void solve(){
que::build();
int k=1,ans=2;
for(int i=n;i>1;i--){
if(que::dec()){ans=i;break;}
}
for(int i=ans-1;i>1;i--){
k^=1;
if(!que::dec())break;
}
cout<<ans-k<<"
";
}
int main(){
// freopen("snakes.in","r",stdin);
// freopen("snakes.out","w",stdout);
int T=read();
for(int tt=1,k,x;tt<=T;tt++){
if(tt==1){
n=read();
for(int i=1;i<=n;i++)A[i]=read();
}
else{
k=read();
for(int i=1;i<=k;i++){
x=read();
A[x]=read();
}
}
solve();
}
return (0-0);
}