CSP-S-2020
T1 儒略日
向T1出題人致以最高的敬意（磕頭），
T2 動物園
簡化題意：給出一些數，保證\(x∈[1,2^k-1]\)且互不相同，給出一些條件，如果存在數\(x\)第\(ai\)位為\(1\)，那么就必須選物品\(bi\)，\(bi\)互不相同，問有多少個數\(y\)滿足不存在\(x=y\)，并且加入\(y\)后選取的\(b\)不變，
很容易發現如果一個條件不被滿足，即不存在數\(x\)第\(ai\)位為1，那么選取的數第\(ai\)位也必須為0，對于給出的\(k\)個位置，假設必須為0的位數有\(c\)個，那么剩下的數就有\(2^{k-c}\)個數加入后不會改變\(b\)的選取，再減去給出的\(n\)個數就得到了答案，
\(n=0,k=64\)的情況要特判，記得開\(unsigned\) \(long\) \(long\)，
#include<bits/stdc++.h>
using namespace std;
#define ll unsigned long long
const int N=1e6+5;
int n,m,c,k;
ll now,t[70];
int a[N];
int main()
{
scanf("%d %d %d %d",&n,&m,&c,&k);
t[0]=1;
for(int i=1;i<=k;++i) t[i]=t[i-1]*2;
now=0;ll x;
for(int i=1;i<=n;++i)
{
scanf("%llu",&x);
now|=x;
}
for(int i=1,b;i<=m;++i) scanf("%d %d",&a[i],&b);
sort(a+1,a+m+1);
a[0]=unique(a+1,a+m+1)-a-1;
int tmp=k;
for(int i=1;i<=a[0];++i)
{
if(a[i]>=tmp) break;
if((now&t[a[i]])==0) k--;
}
if(k==64&&n==0) printf("18446744073709551616");
else printf("%llu",(ll)t[k]-n);
return 0;
}
T3 函式呼叫
個人感覺這道題應該壓軸啊，怎么會是T3，
30pts
線段樹+遞回的做法還是很好想到的，線段樹只維護乘積，每次1操作的時候就先從線段樹把乘積乘下去，再進行1操作，實作是\(O(logn)\)，2操作直接在線段樹根節點乘，實作是O(1)，
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=1e5+5,M=1e6+5;
const ll mod=998244353;
int n,m,Q;
int tot,cz3[M];
struct node{int op,x,y;}cz[N];
ll val[N],mul[N<<2];
void Build(int l,int r,int p)
{
mul[p]=1;
if(l==r) return;
int mid=(l+r)>>1;
Build(l,mid,p<<1);
Build(mid+1,r,p<<1|1);
return;
}
void Spread(int p)
{
if(mul[p]==1) return;
int l=p<<1,r=p<<1|1;
mul[l]=mul[l]*mul[p]%mod;
mul[r]=mul[r]*mul[p]%mod;
mul[p]=1;
return;
}
void Change(int l,int r,int x,ll y,int p)
{
if(l==r)
{
val[l]=(val[l]*mul[p]+y)%mod;
mul[p]=1;
return;
}
Spread(p);
int mid=(l+r)>>1;
if(x<=mid) Change(l,mid,x,y,p<<1);
else Change(mid+1,r,x,y,p<<1|1);
return;
}
void Update(int l,int r,int p)
{
if(l==r)
{
val[l]=val[l]*mul[p]%mod;
return;
}
Spread(p);
int mid=(l+r)>>1;
Update(l,mid,p<<1);
Update(mid+1,r,p<<1|1);
return;
}
void Calc(int pos)
{
if(cz[pos].op==1) Change(1,n,cz[pos].x,(ll)cz[pos].y,1);
else if(cz[pos].op==2) mul[1]=mul[1]*cz[pos].x%mod;
else
{
for(int i=cz[pos].x;i<=cz[pos].y;++i)
Calc(cz3[i]);
}
return;
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;++i) scanf("%lld",&val[i]);
scanf("%d",&m);
for(int i=1;i<=m;++i)
{
scanf("%d",&cz[i].op);
if(cz[i].op==1) scanf("%d %d",&cz[i].x,&cz[i].y);
else if(cz[i].op==2) scanf("%d",&cz[i].x);
else
{
scanf("%d",&Q);
cz[i].x=tot+1;
for(int j=1;j<=Q;++j) scanf("%d",&cz3[tot+j]);
cz[i].y=(tot+=Q);
}
}
Build(1,n,1);
scanf("%d",&Q);
for(int i=1,x;i<=Q;++i)
{
scanf("%d",&x);
Calc(x);
}
Update(1,n,1);
for(int i=1;i<=n;++i) printf("%lld ",val[i]);
return 0;
}
100pts
線段樹做法敗在了3操作可以呼叫3操作，會進行很多重復計算，比如5呼叫2，8呼叫5（2，5，8為編號），最后給出的操作序列：2 5 8，那么操作順序就是：2 5 2 8 5 2，重復呼叫將時間疊上去了，
滿分思路是拓補排序，將每次操作都疊加在呼叫它的操作上，時間復雜度是\(O(n)\)，不太好理解，
這種做法是將加法和乘法分開的，
舉個例子：假設只有一個數\(2\)，先進行\(*3\)操作，再\(+1\)，再\(*2\)，按照之前的思路，計算程序是\((2*3+1)*2\)，加法乘法拆開后計算程序變成\(2*3*2+1*2\)，
因為每個乘法都是作用于整個陣列的，對于一開始給出的陣列，每個數擴大的倍數是一樣的，所以把所有的操作跑一遍之后：\(ai=k*ai\)，
那么先講乘法部分，即如何快速求出這個\(k\)，
乘法部分
首先要明白，最后給出的Q然后又進行一堆操作，可以看成一個3操作，即呼叫別的函式，假設編號為\(m+1\)，
于是把所有操作都向呼叫它的操作連邊，就可以得到一張一定無環的有向圖，（如果存在環，即\(a\)呼叫\(b\)，\(b\)呼叫\(a\)，會陷入死回圈）
給出例圖（為了方便理解，呼叫順序假設都是從左到右呼叫）：
因為每個操作都會被比它后呼叫的操作影響，所以倒著操作的時候可以保證這之后不存在有操作可以影響這個操作，
比如\(*3\)操作，如果后面藍色框框里得到的乘積是\(*5\)，那么現在整張圖的乘積應該是\(*3*15\)，（對應黃路和紫路）
可以看出來，\(*3\)和\(*5\)操作，先算哪一個得到的整張圖的乘積都是一樣的，所以在乘積上，對于同一個操作，左右順序不重要，只需要保證這個操作進行的時候子操作都進行完了就可以了，
（比如給出的例子操作里，藍色框框里要先算最下面的三個點，得到上面的兩個點的值，才能用這兩個點向上面的一個點貢獻\(*5\)）
所有可以用拓補排序按入度為0加入佇列的規則得到操作順序，
然后按這個操作順序每個點向連向的點貢獻乘積即可，
對于沒有被用到的操作，是不存在路徑節點到\(m+1\)的，所有它的貢獻是不會被累積到\(k\)里面的，
代碼實作（寫代碼的時候我的邊是從副操作到子操作，所有統計的是\(out\)）：
inline void add(int u,int v)
{
out[u]++;G[u].push_back(v);F[v].push_back(u);
}
void Init()
{
scanf("%d",&n);
for(int i=1;i<=n;++i) scanf("%lld",&a[i]);
scanf("%d",&m);
for(int i=1;i<=m;++i)
{
scanf("%d %d",&cz[i].op,&cz[i].x);
if(cz[i].op==1) scanf("%d",&cz[i].y);
else if(cz[i].op==3) for(int j=1,v;j<=cz[i].x;++j) scanf("%d",&v),add(i,v);
}
m++;
scanf("%d",&Q);
for(int i=1,v;i<=Q;++i) scanf("%d",&v),add(m,v);
}
void Topo()
{
int l=1;
for(int i=1;i<=m;++i)
if(!out[i]) tq[++tq[0]]=i;
while(l<=tq[0])
{
int u=tq[l++];
int S=F[u].size();
for(int i=0;i<S;++i)
if(!--out[F[u][i]]) tq[++tq[0]]=F[u][i];
}
}
void Update()
{
sum[m]=mul[m]=1;
for(int i=1;i<m;++i) sum[i]=(cz[i].op==2?cz[i].x:1);
for(int i=1;i<=tq[0];++i)
for(int j=0,S=F[tq[i]].size();j<S;++j)
sum[F[tq[i]][j]]=sum[F[tq[i]][j]]*sum[tq[i]]%mod;
for(int i=1;i<=n;++i) a[i]=a[i]*sum[m]%mod;
}
加法部分
如圖，藍色框框代表許多許多操作（2節點在1節點之前還有操作，3在2之前也還有操作，畫上圖太亂了就沒畫），
假設2節點累積值是6，3節點累積值是10，
假設這里有個\(+5\)的操作，受到后面操作的影響，最后加上去的數會變成\(5*60+5*30+5*15\)，（藍，綠，粉），
可以看出來，1直接連向4節點，這個時候23累積上去的乘積是60，所以1節點累加60，
1連向2節點，但2節點有兩種，
2節點直接連向4節點，這時候3累積上的乘積是10，所以2節點累加10，
2節點是連向3節點，3節點連向4節點，無后續影響3節點，此時根節點的累積值是1，所以3累加1，這時候3節點后續有個\(*5\)影響2節點，此時累積到4的積是1，所以在2累加5，
所以2的累加值為\(10+5\)，
1在2這里會被\(*3\)影響，所以1的累加值是\(60+30+15\)，
這樣會發現好像是一個遞回的操作，但其實倒著想可以看成一個從上到下的下放操作，實作極其簡單，代碼非常短，
for(int i=tq[0];i;--i)
for(int j=G[tq[i]].size()-1,ml=1;j>=0;--j)
{
mul[G[tq[i]][j]]=((ll)ml*mul[tq[i]]+mul[G[tq[i]][j]])%mod;
ml=(ll)ml*sum[G[tq[i]][j]]%mod;
}
for(int i=1;i<=n;++i) a[i]=a[i]*sum[m]%mod;
for(int i=1;i<m;++i)
if(cz[i].op==1) a[cz[i].x]=(a[cz[i].x]+cz[i].y*mul[i])%mod;
放上完整代碼：
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=1e5+5;
const ll mod=998244353;
int n,m,Q,out[N],tq[N];
ll a[N],mul[N],sum[N];
struct node{int op,x,y;}cz[N];
vector<int>G[N],F[N];
inline void add(int u,int v)
{
out[u]++;G[u].push_back(v);F[v].push_back(u);
}
void Init()
{
scanf("%d",&n);
for(int i=1;i<=n;++i) scanf("%lld",&a[i]);
scanf("%d",&m);
for(int i=1;i<=m;++i)
{
scanf("%d %d",&cz[i].op,&cz[i].x);
if(cz[i].op==1) scanf("%d",&cz[i].y);
else if(cz[i].op==3) for(int j=1,v;j<=cz[i].x;++j) scanf("%d",&v),add(i,v);
}
m++;
scanf("%d",&Q);
for(int i=1,v;i<=Q;++i) scanf("%d",&v),add(m,v);
}
void Topo()
{
int l=1;
for(int i=1;i<=m;++i)
if(!out[i]) tq[++tq[0]]=i;
while(l<=tq[0])
{
int u=tq[l++];
int S=F[u].size();
for(int i=0;i<S;++i)
if(!--out[F[u][i]]) tq[++tq[0]]=F[u][i];
}
}
void Update()
{
sum[m]=mul[m]=1;
for(int i=1;i<m;++i) sum[i]=(cz[i].op==2?cz[i].x:1);
for(int i=1;i<=tq[0];++i)
for(int j=0,S=F[tq[i]].size();j<S;++j)
sum[F[tq[i]][j]]=sum[F[tq[i]][j]]*sum[tq[i]]%mod;
for(int i=tq[0];i;--i)
for(int j=G[tq[i]].size()-1,ml=1;j>=0;--j)
{
mul[G[tq[i]][j]]=((ll)ml*mul[tq[i]]+mul[G[tq[i]][j]])%mod;
ml=(ll)ml*sum[G[tq[i]][j]]%mod;
}
for(int i=1;i<=n;++i) a[i]=a[i]*sum[m]%mod;
for(int i=1;i<m;++i)
if(cz[i].op==1) a[cz[i].x]=(a[cz[i].x]+cz[i].y*mul[i])%mod;
}
int main()
{
Init();
Topo();
Update();
for(int i=1;i<=n;++i) printf("%lld ",a[i]);
}
T4 貪吃蛇
如果蛇A吃了蛇B后，會被別的蛇吃掉，那他就不會吃B，那么假設所有蛇都不聰明，那么當被吃掉的蛇，假設為A，A吃過別的蛇，假設被A吃的是B，那么A當初就不會吃B，因為它吃了B后會被別的蛇吃掉，所以每個蛇吃別的蛇的時候，都儲存一下如果這個蛇沒有吃的話現在還剩了幾條蛇，吃到第一條吃過別的蛇的蛇就回傳這個的儲存值，
可以用\(set\)，平衡樹來快速插入洗掉，
但時間復雜度是A不了的，可以拿大部分分，
每次被吃掉的蛇一定是沒有吃過別的蛇的，就是在初始陣列的蛇，所以被吃的蛇一定是嚴格遞增，這個遞增是指按題上的大小排序，
另開一個陣列q來儲存A吃B之后的值，每次拿出來吃別的蛇的蛇一定嚴格遞減，所以吃完之后的得到的值也是嚴格遞減，保證了q的單調性，每次最大的要么是q的要么是原始陣列里的，每次最小的只能是原始陣列的，如果q的最小值比原始陣列小，本次計算就結束了，
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/208600.html
標籤：其他
上一篇：微信小程式開發之云開發
下一篇：技術點5：XML語言