T1 [NOIP2017 提高组] 时间复杂度
大模拟……
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int t,n,k,as,nw,tr,ed[105];
int c[26],str[105],b[105];
string tim;
stack<int>st;
struct Aadd{
string s,t,fr,ed;
}ad[105];
int dfs(int x){
int mx=0;b[x]=1;
for(int i=x+1;str[i]<=ed[x]&&i<=tr;i++)
if(!b[i]) mx=max(mx,dfs(i));
if(ad[str[x]].fr!="n"&&ad[str[x]].ed=="n") mx++;
if(ad[str[x]].fr=="n"&&ad[str[x]].ed!="n") mx=0;
if(ad[str[x]].fr!="n"&&ad[str[x]].ed!="n"){
int e=0,f=0;
for(int i=0;i<ad[str[x]].fr.size();i++)
e=e*10+ad[str[x]].fr[i]-'0';
for(int i=0;i<ad[str[x]].ed.size();i++)
f=f*10+ad[str[x]].ed[i]-'0';
if(e>f) mx=0;
}return mx;
}void zjy(){
memset(c,0,sizeof(c));
memset(b,0,sizeof(b));
while(st.size()) st.pop();
cin>>n>>tim;
k=as=nw=tr=0;int f=0;
if(tim!="O(1)"){
int ln=tim.size();
for(int i=0;i<ln;i++)
if(tim[i]<='9'&&tim[i]>='0')
k=k*10+tim[i]-'0';
}for(int i=1;i<=n;i++){
cin>>ad[i].s;
if(ad[i].s=="E"){
if(st.size()){
ed[c[st.top()]]=i;
c[st.top()]=0;
st.pop();
}f--;
}else{
str[++tr]=i;
cin>>ad[i].t>>ad[i].fr>>ad[i].ed;
f++;st.push(ad[i].t[0]-'a');
if(c[ad[i].t[0]-'a']) f=-1e9;
c[ad[i].t[0]-'a']=tr;
}if(f<0) f=-1e9;
}if(f){
cout<<"ERR\n";
return;
}for(int i=1;i<=tr;i++){
if(b[i]) continue;
int df=dfs(i);
as=max(as,df);
}if(as==k) cout<<"Yes\n";
else cout<<"No\n";
}int main(){
cin>>t;
while(t--) zjy();
return 0;
}
T2 [CSP-S2019] Emiya 家今天的饭
考虑求出每种做法选一道，菜没有限制的值 \(ans\)，和每种做法选一道，必须有一种菜超过一半的值 \(sum\)，则答案为 \(ans-sum\)。
容易发现 \(ans=\prod\limits_{i=1}^n(s_i+1)-1\)，其中 \(s_i=\sum\limits_{j=1}^ma_{i,j}\)。
\(sum\) 考虑用 \(dp\) 求。对于每种菜 \(c\) 超过一半的可能性，设 \(dp_{i,j}\) 表示目前处理到第 \(i\) 种做法，\(c\) 这种菜要比其他菜多用 \(j\) 次，则有：
\[dp_{i,j}=dp_{i-1,j}+dp_{i-1,j-1}\times a_{i,c}+dp_{i-1,j+1}\times(s_i-a_{i,c}) \]设 \(k_i=\sum\limits_{j=1}^ndp_{n,j}\)，则 \(sum=\sum\limits_{c=1}^mk_c\)。
时间复杂度为 \(O(n^2m)\)。
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll p=998244353;
int n,m;
ll a[105][2005],ans=1;
ll s[105],dp[105][205];
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>a[i][j];
s[i]=(s[i]+a[i][j]+p)%p;
}ans=ans*(s[i]+1)%p;
}for(int c=1;c<=m;c++){
memset(dp,0,sizeof(dp));
dp[0][n]=1;
for(int i=1;i<=n;i++)
for(int j=n-i;j<=n+i;j++)
dp[i][j]=(dp[i-1][j]+dp[i-1][j-1]*a[i][c]+dp[i-1][j+1]*(s[i]-a[i][c]+p)%p)%p;
for(int i=n+1;i<=n*2;i++) ans=(ans+p-dp[n][i])%p;
}cout<<(ans-1+p)%p;
return 0;
}
T3 [yLOI2020] 凉凉
看 \(n\) 明显状压。
设 \(dp_{i,s}\) 表示当考虑到的深度为 \(i\)，现在处理线路的状态为 \(s\) 时的最小花费，\(g_{i,s}\) 表示将状态为 \(s\) 的铁路全部塞在第 \(i\) 层所需的花费，则有：
\[dp_{i,s}=\min\limits_{t\in s}(dp_{i-1,s\oplus t}+g_{i,t}) \]时间复杂度似乎是 \(O(m+3^nn)\)（来自洛谷的官方题解）。
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e5+5,M=(1<<14);
int n,m,tp,st[15],a[15][N];
int vis[15][15],k[15],b[15][N];
ll c[15][15],g[15][M],dp[15][M];
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
cin>>a[i][j];
for(int i=1;i<=n;i++){
cin>>k[i];
for(int j=1;j<=k[i];j++){
cin>>b[i][j];
for(int l=1;l<=n;l++)
c[i][l]+=a[l][b[i][j]];
}sort(b[i]+1,b[i]+1+k[i]);
}for(int i=1;i<=n;i++)
for(int j=i+1;j<=n;j++){
int x=1,y=1,f=1;
while(x<=k[i]&&y<=k[j]){
if(b[i][x]==b[j][y]){
f=0;break;
}if(b[i][x]>b[j][y]) y++;
else x++;
}if(f) vis[i][j]=vis[j][i]=1;
}
for(int s=1;s<(1<<n);s++,tp=0)
for(int i=1;i<=n;i++)
if(s&(1<<(i-1))){
st[++tp]=i;
for(int j=1;j<tp;j++)
if(!vis[i][st[j]])
for(int l=1;l<=n;l++)
g[l][s]=1e18+1;
if(dp[1][s]==1e18+1) break;
for(int j=1;j<=n;j++)
g[j][s]+=c[i][j];
}for(int s=1;s<(1<<n);s++)
dp[1][s]=g[1][s];
for(int i=2;i<=n;i++)
for(int s=0;s<(1<<n);s++){
dp[i][s]=dp[i-1][s];
for(int t=s;t;t=(t-1)&s)
dp[i][s]=min(dp[i][s],dp[i-1][s^t]+g[i][t]);
}
cout<<dp[n][(1<<n)-1]<<"\n";
return 0;
}
T4 [联合省选 2020 A]树
这里用的是洛谷该题的第一种神仙题解。
考虑在连续一段数的二进制，他的第 \(i\) 位（将个位视为第 \(0\) 位）规律为： \(2^i\) 位 \(1\)，\(2^i\) 位 \(0\)。
考虑单独对每一位进行处理。
实际上，假如用树上差分，时间复杂度会降低，并且，每一段受影响区域的开头的深度对 \(2^i\) 同余。
所以可以将差分数组设为 \(w_{i,j}\)，表示正在枚举第 \(i\) 位，深度 \(\bmod 2^i=j\)。
用一个 \(dfs\) 即可解决，时间复杂度 \(O(n\log n)\)。
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll rd(){
ll x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9') ch=='-'&&(f=-1),ch=getchar();
while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
return x*f;
}const int N=(1<<21);
int n,m,h[N],to[N],nxt[N];
ll v[N],w[21][N],ans=0;
void add(int x,int y){
to[++m]=y;
nxt[m]=h[x];
h[x]=m;
}ll dfs(int x,ll y){
ll sum=v[x];
for(int i=0;i<21;i++)
w[i][(y+v[x])&((1ll<<i)-1ll)]^=1ll<<i;
for(int i=0;i<21;i++)
sum^=w[i][y&((1ll<<i)-1ll)];
for(int i=h[x];i;i=nxt[i])
sum^=dfs(to[i],y+1);
for(int i=0;i<21;i++)
sum^=w[i][y&((1ll<<i)-1ll)];
ans+=sum;return sum;
}int main(){
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);n=rd();
for(int i=1;i<=n;i++) v[i]=rd();
for(int i=2;i<=n;i++) add(rd(),i);
dfs(1,0);cout<<ans;
return 0;
}