我們剛剛知道那些題的解法-7
ZR2423
一個第一次見到的套路：我們考慮轉化一下兩個兒子都走這個選擇，我們可以考慮建第三個兒子，它的子樹中的每個節點的權值等于之前兩個兒子對應權值的異或和，則顯然，如果接下來沒有選擇兩個兒子都走的話，走第三個兒子正確性是顯然的，如果又選擇了兩個兒子都走，那么就可以對于某個節點再建第三個兒子。
綜上，我們可以把二叉樹擴展成三叉樹，這樣第三個選擇就變成了走第三個兒子，DP 算出 \(f_{k,0/1}\) 表示 \(k\) 結點往下先手能否得到 \(0\) 和 \(1\)，即偶數或者是奇數，轉移就考慮假設 \(a_k=0\)，如果 \(k\) 想得到 \(0\)，至少有一個兒子得不到 \(1\)。\(a_k=1\) 同理。
#include<bits/stdc++.h>
#define mset(a,b) memset((a),(b),sizeof((a)))
#define rep(i,l,r) for(int i=(l);i<=(r);i++)
#define dec(i,l,r) for(int i=(r);i>=(l);i--)
#define cmax(a,b) (((a)<(b))?(a=b):(a))
#define cmin(a,b) (((a)>(b))?(a=b):(a))
#define Next(k) for(int x=head[k];x;x=li[x].next)
#define vc vector
#define ar array
#define pi pair
#define fi first
#define se second
#define mp make_pair
#define pb emplace_back
#define N 20000010
#define M number
using namespace std;
typedef double dd;
typedef long double ld;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
//#define int long long
typedef pair<int,int> P;
typedef vector<int> vi;
const int INF=0x3f3f3f3f;
const dd eps=1e-9;
template<typename T> inline void read(T &x) {
x=0; int f=1;
char c=getchar();
for(;!isdigit(c);c=getchar()) if(c == '-') f=-f;
for(;isdigit(c);c=getchar()) x=x*10+c-'0';
x*=f;
}
int ch[N][3],ans[N][2],n,a[N],rt,tot;
bool vis[N];
inline void add(int x,int y,int z){
a[z]=a[x]^a[y];
if(!ch[x][0]) return;
ch[z][0]=++tot;ch[z][1]=++tot;
add(ch[x][0],ch[y][0],ch[z][0]);
add(ch[x][1],ch[y][1],ch[z][1]);
}
inline void build(int k){
ch[k][2]=++tot;
add(ch[k][0],ch[k][1],ch[k][2]);
if(!ch[k][0]) return;
build(ch[k][0]);build(ch[k][1]);build(ch[k][2]);
}
inline void dfs(int k){
if(!ch[k][0]){
if(a[k]) ans[k][1]=1;
else ans[k][0]=1;
return;
}
dfs(ch[k][0]);dfs(ch[k][1]);dfs(ch[k][2]);
rep(i,0,2) ans[k][0]|=(ans[ch[k][i]][1]==0);
rep(i,0,2) ans[k][1]|=(ans[ch[k][i]][0]==0);
if(a[k]) swap(ans[k][0],ans[k][1]);
}
int main(){
// freopen("my.in","r",stdin);
// freopen("my.out","w",stdout);
read(n);tot=n;
rep(i,1,n){
int l,r,c;read(l);read(r);read(c);
vis[l]=vis[r]=1;a[i]=c;
ch[i][0]=l;ch[i][1]=r;
}
rep(i,1,n) if(!vis[i]){rt=i;break;}
build(rt);dfs(rt);
rep(i,1,n){
if(ans[i][0]) puts("Alice");
else puts("Bob");
}
}
ZR2438
考慮 \(k=2\)，一定是 \(aabaa\)，考慮 \(k=3\)，一定是先有一個 \(bbcbb\)，然后往里盡可能少的插入 \(a\)，且盡可能字典序最小，使得合法。
我們在最前面放一個 \(aa\)，然后再每一個 \(b\) 后面都放上一個 \(a\)，在最后放一個 \(aa\)，然后再每個 \(b\) 前面都有一個 \(a\)，最后只需要保證兩個相鄰的 \(b\) 之間只有一個 \(a\)，這樣顯然是最優的，若只看 \(a,b\)，我們構造出來的答案應該是 \(aababababaa\)，考慮放 \(c\)，顯然有 \(aababacbabaa\)。用這種思路可以構造出 \(k\) 其余情況，然后考慮每個字母的填的個數是等差數列上升的，可以算出序列長度。然后找輸出規律可以簡化代碼。
#include<bits/stdc++.h>
#define mset(a,b) memset((a),(b),sizeof((a)))
#define rep(i,l,r) for(int i=(l);i<=(r);i++)
#define dec(i,l,r) for(int i=(r);i>=(l);i--)
#define cmax(a,b) (((a)<(b))?(a=b):(a))
#define cmin(a,b) (((a)>(b))?(a=b):(a))
#define Next(k) for(int x=head[k];x;x=li[x].next)
#define vc vector
#define ar array
#define pi pair
#define fi first
#define se second
#define mp make_pair
#define pb emplace_back
#define N number
#define M number
using namespace std;
typedef double dd;
typedef long double ld;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
//#define int long long
typedef pair<int,int> P;
typedef vector<int> vi;
const int INF=0x3f3f3f3f;
const dd eps=1e-9;
template<typename T> inline void read(T &x) {
x=0; int f=1;
char c=getchar();
for(;!isdigit(c);c=getchar()) if(c == '-') f=-f;
for(;isdigit(c);c=getchar()) x=x*10+c-'0';
x*=f;
}
int t,n,Q;
int main(){
read(t);
while(t--){
read(n);read(Q);
int m=(1+(1+(Q-1)*3))*Q/2;
if(n<m){puts("-1");continue;}
if(Q==1){
rep(i,1,n) putchar('a');
puts("");
continue;
}
rep(i,m+1,n) putchar('a');
rep(i,1,Q-1){
dec(j,0,i-1) putchar('a'+j);
dec(j,0,i-1) putchar('a'+j);
}
putchar('a'+Q-1);
dec(j,0,Q-2) putchar('a'+j);
dec(i,1,Q-1){
dec(j,0,i-1) putchar('a'+j);
}
puts("");
}
return 0;
}
ZR2440
考慮一個 DP，設 dfs(k,v1,v2,s) 表示目前填到了 \(k\)，并且 \(k\) 填在點 \(v1\) 上，\(k-1\) 填在點 \(v2\) 上，目前填過數的點為 \(s\)，發現這個加個記憶化就過了。
轉移的話暴力枚舉下一個數填在哪里即可。
為什么？因為其實所有合法的狀態是在可接受范圍內。首先填完 \(k+1\) 之后必須要滿足 \(v2\) 被填完，并且這個狀態必須滿足把整棵樹中的 \(v1,v2\) 刪掉之后，其余的連通塊，要么都填上數了，要么都沒填。因為每個點的度數最多為 \(4\)，所以復雜度為 \(n^32^7\)。
#include<bits/stdc++.h>
#define mset(a,b) memset((a),(b),sizeof((a)))
#define rep(i,l,r) for(int i=(l);i<=(r);i++)
#define dec(i,l,r) for(int i=(r);i>=(l);i--)
#define cmax(a,b) (((a)<(b))?(a=b):(a))
#define cmin(a,b) (((a)>(b))?(a=b):(a))
#define Next(k) for(int x=head[k];x;x=li[x].next)
#define vc vector
#define ar array
#define pi pair
#define fi first
#define se second
#define mp make_pair
#define pb emplace_back
#define N 61
#define M number
using namespace std;
typedef double dd;
typedef long double ld;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
#define int long long
typedef pair<int,int> P;
typedef vector<int> vi;
const int INF=0x3f3f3f3f;
const dd eps=1e-9;
const int mod=1e9+7;
template<typename T> inline void read(T &x) {
x=0; int f=1;
char c=getchar();
for(;!isdigit(c);c=getchar()) if(c == '-') f=-f;
for(;isdigit(c);c=getchar()) x=x*10+c-'0';
x*=f;
}
int n;
vi e[N];
bool vis[N];
unordered_map<int,int> f[N][N][N];
inline bool Dfs(int s,int k,int fat){
for(int to:e[k]){
if(to==fat||vis[to]==1) continue;
if(!Dfs(s,to,k)) return 0;
if(fat!=0){
if(((s>>(to-1))&1)!=((s>>(k-1))&1)) return 0;
}
}
return 1;
}
inline bool chk(int s,int a,int b){
vis[a]=1;vis[b]=1;
if(!Dfs(s,a,0)){
// printf("a=%d BAN\n",a);
return 0;
}
if(!Dfs(s,b,0)){
// printf("b=%d BAN\n",b);
return 0;
}
vis[a]=0;vis[b]=0;
return 1;
}
//v1 is k, v2 is k-1
//s is used
inline int dfs(int k,int v1,int v2,int s){
// printf("Enter: k=%d v1=%d v2=%d s=%d\n",k,v1,v2,s);
if(k==n){
// printf("k=%d\n",k);
return 1;
}
// puts("Here");
if(f[k][v1][v2].find(s)!=f[k][v1][v2].end()) return f[k][v1][v2][s];
// puts("Here");
// f[k][v1][v2][s]=0;
int &ans=f[k][v1][v2][s];
ans=0;
// puts("Here");
if(v1&&v2&&!chk(s,v1,v2)){
ans=0;
// printf("chk no k=%d v1=%d v2=%d s=%d\n",k,v1,v2,s);
return 0;
}
// puts("Here");
if(v2==0){
rep(i,0,n-1){
if((s>>i)&1) continue;
int nw=i+1;
ans=(ans+dfs(k+1,nw,v1,s|(1ll<<i)))%mod;
}
}
else{
int cnt=0,id=-1;
for(int to:e[v2]){
if(((s>>(to-1))&1)==0){
cnt++;id=to;
}
}
if(cnt>1){
// printf("cnt>1 k=%d v1=%d v2=%d s=%d\n",k,v1,v2,s);
return (ans=0);
}
if(cnt==1){
ans=(ans+dfs(k+1,id,v1,s|(1ll<<(id-1))))%mod;
}
else{
rep(i,0,n-1){
if((s>>i)&1) continue;
int nw=i+1;
ans=(ans+dfs(k+1,nw,v1,s|(1ll<<i)))%mod;
}
}
}
// printf("End: k=%d v1=%d v2=%d s=%d ans=%d\n",k,v1,v2,s,ans);
return ans;
}
signed main(){
// freopen("my.in","r",stdin);
// freopen("my.out","w",stdout);
read(n);
rep(i,1,n-1){
int u,v;read(u);read(v);e[u].pb(v);e[v].pb(u);
}
int Ans=dfs(0,0,0,0);
printf("%lld\n",Ans);
return 0;
}
ZR2370
二分答案，考慮構造出來一個序列是困難的，所以我們不妨想把從原序列刪數制止合法。首先顯然是把數字從大往小刪，如果一個數與它左右相鄰的數不合法，那么就刪掉，用一個鏈表來維護刪除即可。
#include<bits/stdc++.h>
#define mset(a,b) memset((a),(b),sizeof((a)))
#define rep(i,l,r) for(int i=(l);i<=(r);i++)
#define dec(i,l,r) for(int i=(r);i>=(l);i--)
#define cmax(a,b) (((a)<(b))?(a=b):(a))
#define cmin(a,b) (((a)>(b))?(a=b):(a))
#define Next(k) for(int x=head[k];x;x=li[x].next)
#define vc vector
#define ar array
#define pi pair
#define fi first
#define se second
#define mp make_pair
#define pb emplace_back
#define N 500010
#define M number
using namespace std;
typedef double dd;
typedef long double ld;
typedef unsigned int uint;
typedef unsigned long long ull;
#define ll long long
typedef pair<int,int> P;
typedef vector<int> vi;
const int INF=0x3f3f3f3f;
const dd eps=1e-9;
template<typename T> inline void read(T &x) {
x=0; int f=1;
char c=getchar();
for(;!isdigit(c);c=getchar()) if(c == '-') f=-f;
for(;isdigit(c);c=getchar()) x=x*10+c-'0';
x*=f;
}
int n,K,a[N],L[N],R[N],b[N];
inline void del(int k){
R[L[k]]=R[k];
L[R[k]]=L[k];
}
inline bool chk(int mid){
rep(i,1,n) L[i]=i-1,R[i]=i+1;
R[n]=1;L[1]=n;
int tot=n;
rep(i,1,n){
int l=L[b[i]],r=R[b[i]];
if(a[l]+a[b[i]]>mid||a[r]+a[b[i]]>mid) del(b[i]),tot--;
}
return tot>=K;
}
signed main(){
// freopen("my.in","r",stdin);
// freopen("my.out","w",stdout);
read(n);read(K);rep(i,1,n) read(a[i]);
rep(i,1,n) b[i]=i;
sort(b+1,b+n+1,[&](int i,int j){return a[i]>a[j];});
ll l=1,r=2e9;
while(l<r){
// printf("l=%d r=%d\n",l,r);
int mid=(l+r)>>1;
if(chk(mid)) r=mid;
else l=mid+1;
}
printf("%lld\n",l);
return 0;
}
ZR2446
首先我們可以固定一個左端點，接下來就是選擇一個右端點。
容易發現，右端點的選取與一些后綴之間的排序有關，但是這些后綴后面還有可能會接一些東西， 場上一直在想 SA，這就導致了這個題沒有思路。
但實際上，后面的那些接上去的東西，一樣是字符串的一些后綴，而他們的哈希值都是可以提前預處理出來的，這提示我們可以在 \(\log\) 的時間復雜度比較出兩個字符串的大小。
ZR2448
首先可以建出括號序，而我們的路徑很像是先往祖先走，然后按著兄弟走，然后再往下走，大致這樣的一個過程。
于是我們可以預處理出每個點走 \(2^i\) 步能夠走到的最左邊最右邊的點是什么。
注意程序中的預處理。這樣預處理的正確性可以歸納證明，若 \(i-1\) 時的值都是我們想要的，考慮 \(i\) 時的值，只需要考慮前 \(2^{i-1}\) 步到底是想要走到一個最左邊的點，還是最右邊的點，由于括號序列的特殊性，如果往左邊走，那么走到最左邊一定是最優的，如果往右邊走，那么走到最右邊一定是最優的。
這個證明非常不嚴謹，但是感受一下應該是對的，目前博主才疏學淺并不能夠證明，但是感性理解盡可能往左走和盡可能往右走總有一個是正確的。
由此，我們接下來對于每個詢問相當于讓 \(x,y\) 都走到 \(x,y\) 之間的一個任意一個點即可，只要這個點在最優路徑上，就可以保證正確性，我們只需要從 \(x\) 開始，盡可能往 \(y\) 走而不超過 \(y\) 即可，然后接下來再讓 \(y\) 走，這相當于在能走的情況下讓 \(x\) 走到盡可能往右的點，根據上面的正確性，我們要維護兩個值，一個是往左走的最優值，一個是往右走的最優值。
#include<bits/stdc++.h>
#define mset(a,b) memset((a),(b),sizeof((a)))
#define rep(i,l,r) for(int i=(l);i<=(r);i++)
#define dec(i,l,r) for(int i=(r);i>=(l);i--)
#define cmax(a,b) (((a)<(b))?(a=b):(a))
#define cmin(a,b) (((a)>(b))?(a=b):(a))
#define Next(k) for(int x=head[k];x;x=li[x].next)
#define vc vector
#define ar array
#define pi pair
#define fi first
#define se second
#define mp make_pair
#define pb emplace_back
#define N 400010
#define M number
using namespace std;
typedef double dd;
typedef long double ld;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
//#define int long long
typedef pair<int,int> P;
typedef vector<int> vi;
const int INF=0x3f3f3f3f;
const dd eps=1e-9;
template<typename T> inline void read(T &x) {
x=0; int f=1;
char c=getchar();
for(;!isdigit(c);c=getchar()) if(c == '-') f=-f;
for(;isdigit(c);c=getchar()) x=x*10+c-'0';
x*=f;
}
char s[N];
int sta[N],top,n,a[N],L[N][21],R[N][21],m;
int main(){
// freopen("my.in","r",stdin);
// freopen("my.out","w",stdout);
scanf("%s",s+1);
n=strlen(s+1);
rep(i,1,n){
if(s[i]=='(') sta[++top]=i;
else{
a[i]=sta[top];
a[sta[top]]=i;
top--;
}
}
rep(i,1,n){
L[i][0]=max(min(i-1,a[i]),0);
R[i][0]=min(max(i+1,a[i]),n);
}
rep(j,1,20){
rep(i,1,n){
L[i][j]=min(L[L[i][j-1]][j-1],L[R[i][j-1]][j-1]);
R[i][j]=max(R[R[i][j-1]][j-1],R[L[i][j-1]][j-1]);
}
}
read(m);
rep(i,1,m){
int x,y;read(x);read(y);
if(x==y){
puts("0");continue;
}
if(x>y) swap(x,y);
int l,r;
l=r=x;
int ans=0;
dec(i,0,20){
int nl=min(L[l][i],L[r][i]);
int nr=max(R[l][i],R[r][i]);
if(nr<y){
l=nl;r=nr;ans+=(1<<i);
}
}
x=r;l=r=y;
// printf("ans=%d x=%d\n",ans,x);
dec(i,0,20){
int nl=min(L[l][i],L[r][i]);
int nr=max(R[l][i],R[r][i]);
// printf("i=%d nl=%d nr=%d\n",i,nl,nr);
if(nl>x){
l=nl;r=nr;ans+=(1<<i);
}
}
// printf("ans=%d l=%d\n",ans,l);
ans++;
printf("%d\n",ans);
}
return 0;
}
ZR2457
原題：LOJ 花火
考慮能夠作為左端點的值一定是前綴 \(\max\) 所在點，能夠作為右端點的值一定是后綴 \(\min\) 的所在點，而交換這兩個點的貢獻等價于把 \((i,a_i)\) 放在二維平面上，以 \((l,a_l)\) 作為左上角 \((r,a_r)\) 作為右下角內部矩形的點的個數乘上 \(2\) 再加 \(1\)。
這樣一共還是要做 \(n^2\) 次矩陣詢問，不妨考慮內部一個點能夠做貢獻的區間，不難發現點 \((i,a_i)\) 能夠做貢獻的點對對于左端點和右端點都是一段區間，也就是一個矩形，這轉化成了 \(n\) 個矩形加，求全局最大值。求操作區間需要二分，其余掃描線即可。
#include<bits/stdc++.h>
#define mset(a,b) memset((a),(b),sizeof((a)))
#define rep(i,l,r) for(int i=(l);i<=(r);i++)
#define dec(i,l,r) for(int i=(r);i>=(l);i--)
#define cmax(a,b) (((a)<(b))?(a=b):(a))
#define cmin(a,b) (((a)>(b))?(a=b):(a))
#define Next(k) for(int x=head[k];x;x=li[x].next)
#define vc vector
#define ar array
#define pi pair
#define fi first
#define se second
#define mp make_pair
#define pb emplace_back
#define N 1000100
#define M number
using namespace std;
typedef double dd;
typedef long double ld;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
//#define int long long
typedef pair<int,int> P;
typedef vector<int> vi;
const int INF=0x3f3f3f3f;
const dd eps=1e-9;
template<typename T> inline void read(T &x) {
x=0; int f=1;
char c=getchar();
for(;!isdigit(c);c=getchar()) if(c == '-') f=-f;
for(;isdigit(c);c=getchar()) x=x*10+c-'0';
x*=f;
}
int n,a[N],b[N],c[N];
struct Ques{
int l,r,v;
inline Ques(){}
inline Ques(int l,int r,int v) : l(l),r(r),v(v) {}
};
vc<Ques> q[N];
struct Node{
int maxx,tag;
}p[N<<2];
struct SegmentTree{
#define ls(k) k<<1
#define rs(k) k<<1|1
inline void pushup(int k){
p[k].maxx=max(p[ls(k)].maxx,p[rs(k)].maxx);
}
inline void A(int k,int x){
p[k].maxx+=x;
p[k].tag+=x;
}
inline void pushdown(int k){
if(p[k].tag){
A(ls(k),p[k].tag);A(rs(k),p[k].tag);p[k].tag=0;
}
}
inline void change(int k,int l,int r,int z,int y,int x){
if(z<=l&&r<=y){
A(k,x);return;
}int mid=(l+r)>>1;pushdown(k);
if(z<=mid) change(ls(k),l,mid,z,y,x);
if(mid<y) change(rs(k),mid+1,r,z,y,x);
pushup(k);
}
}st;
inline int binale(int l,int r,int v,int *f){
if(l>r) return -1;
while(l<r){
int mid=(l+r+1)>>1;
if(a[f[mid]]<=v) l=mid;
else r=mid-1;
}
if(a[f[l]]<=v) return l;
return -1;
}
inline int binage(int l,int r,int v,int *f){
if(l>r) return -1;
while(l<r){
int mid=(l+r)>>1;
if(a[f[mid]]>=v) r=mid;
else l=mid+1;
}
if(a[f[l]]>=v) return l;
return -1;
}
int main(){
// freopen("my.in","r",stdin);
// freopen("my.out","w",stdout);
read(n);rep(i,1,n) read(a[i]);
b[1]=1;
rep(i,2,n){
if(a[i]>a[b[i-1]]) b[i]=i;
else b[i]=b[i-1];
}
c[n]=n;
dec(i,1,n-1){
if(a[i]<a[c[i+1]]) c[i]=i;
else c[i]=c[i+1];
}
rep(i,1,n){
int l=binage(1,i-1,a[i],b);
int r=binale(i+1,n,a[i],c);
// printf("i=%d l=%d r=%d\n",i,l,r);
if(l==-1||r==-1) continue;
q[l].pb(i+1,r,2);q[i].pb(i+1,r,-2);
// printf("id=%d l=%d r=%d v=%d\n",l,i+1,r,2);
// printf("id=%d l=%d r=%d v=%d\n",i,i+1,r,-2);
}
// rep(i,1,n){
// int l=binale(1,i-1,a[i],b);
// int r=binale(i+1,n,a[i],c);
// if(l==-1||r==-1) continue;
// printf("i=%d\n",i);
// q[1].pb(i+1,r,-1);q[l+1].pb(i+1,r,1);
// printf("id=%d l=%d r=%d v=%d\n",1,i+1,r,-1);
// printf("id=%d l=%d r=%d v=%d\n",l+1,i+1,r,1);
// }
// rep(i,1,n){
// int l=binage(1,i-1,a[i],b);
// int r=binage(i+1,n,a[i],c);
// if(l==-1||r==-1) continue;
// printf("i=%d\n",i);
// q[l].pb(r,n,-1);q[i].pb(r,n,1);
// printf("id=%d l=%d r=%d v=%d\n",l,r,n,-1);
// printf("id=%d l=%d r=%d v=%d\n",i,r,n,1);
// }
int ans=0;
rep(i,1,n){
for(Ques now:q[i]){
st.change(1,1,n,now.l,now.r,now.v);
}
ans=max(ans,p[1].maxx);
}
printf("%d\n",ans+1);
return 0;
}
ZR2459
若給定排列，如果加油量減耗油量小于 \(0\)，那么答案一定為 \(0\)，否則我們把從 \(1\) 開始的折線畫出來，發現如果以最靠左的最小值作為開始點一定能滿足條件。
設這個折線上的點為 \(S\)，那么從 \(S\) 往左走是一個總大于 \(0\) 的折線，向右走是一個總大于等于 \(0\) 的折線，考慮預處理 \(f_s\) 表示用 \(s\) 中的點湊成一條大于 \(0\) 的折線，\(g_s\) 表示用 \(s\) 中的帶你湊成一條大于等于 \(0\) 的折線，然后就可以計算答案了。
考慮如何計算 \(f_s\)，首先從 \(S\) 往左走，相當于把之前的操作反號，所以要求是 \(sum_s<0\)，因為加點一定是往左邊加，所以我們不妨枚舉最后一個加進來的點，直接加即可，需要滿足去掉最后一個加進來的點，剩下的也滿足 \(sum<0\)，這樣才能滿足加點前后總是大于 \(0\)。
\(g_s\) 的轉移同樣分析即可。
#include<bits/stdc++.h>
#define mset(a,b) memset((a),(b),sizeof((a)))
#define rep(i,l,r) for(int i=(l);i<=(r);i++)
#define dec(i,l,r) for(int i=(r);i>=(l);i--)
#define cmax(a,b) (((a)<(b))?(a=b):(a))
#define cmin(a,b) (((a)>(b))?(a=b):(a))
#define Next(k) for(int x=head[k];x;x=li[x].next)
#define vc vector
#define ar array
#define pi pair
#define fi first
#define se second
#define mp make_pair
#define pb emplace_back
#define N 21
#define M 2000100
using namespace std;
typedef double dd;
typedef long double ld;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
#define int long long
typedef pair<int,int> P;
typedef vector<int> vi;
const int INF=0x3f3f3f3f;
const dd eps=1e-9;
const int mod=1e9+7;
template<typename T> inline void read(T &x) {
x=0; int f=1;
char c=getchar();
for(;!isdigit(c);c=getchar()) if(c == '-') f=-f;
for(;isdigit(c);c=getchar()) x=x*10+c-'0';
x*=f;
}
int n,a[N],b[N],c[N],f[M],g[M],sum[M];
signed main(){
// freopen("my.in","r",stdin);
// freopen("my.out","w",stdout);
read(n);rep(i,1,n) read(a[i]),read(b[i]),c[i]=a[i]-b[i];
rep(i,1,n) sum[(1<<(i-1))]=c[i];
rep(i,0,(1<<n)-1){
sum[i]=sum[i&(-i)]+sum[i^(i&(-i))];
}
if(sum[(1<<n)-1]<0){puts("0");return 0;}
g[0]=f[0]=1;
rep(i,0,(1<<n)-1){
if(sum[i]>=0){
rep(j,0,n-1) if((i>>j)&1) (g[i]+=g[i^(1<<j)])%=mod;
}
else{
rep(j,0,n-1) if((i>>j)&1) (f[i]+=f[i^(1<<j)])%=mod;
}
}
int ans=0;
rep(i,0,(1<<n)-1){
ans=(ans+f[i]*g[((1<<n)-1)^i]%mod*(__builtin_popcountll(i)+1)%mod)%mod;
}
printf("%lld\n",ans);
return 0;
}
ZR2458
這里只說明 \(80\) 分做法，首先考慮容斥，首先如果在兩個不能相鄰的點之間連邊，限制成一條鏈，我們一定是欽定有 \(i\) 對點不滿足條件，而這 \(i\) 對點不滿足條件，等價于把那條長度為 \(m\) 的限制鏈劃分成 \(m-i\) 段，我們先填這些欽定的東西，然后把每個劃分出來鏈看做一個整體，與剩下的做一個全排列，于是我們有：
\[\sum\limits_{i=0}^mf_{m,i}(n-m+i)!(-1)^{m-i}
\]
其中，\(f_{m-i}\) 可以在 \(m^2\) 時間復雜度內算出，\(f_{m,i}\) 表示把一條長度為 \(m\) 的鏈劃分成 \(i\) 段的方案數。
瓶頸在求階乘上，不過我們可以利用分塊打表，在可以接受的時間復雜度內預處理所有可能需要的階乘。
ZR2461
場上想用線段樹合并來維護每個節點的值，其實不用，依然是從大往小加邊的思路，不過我們只需要維護連通塊內答案最小的點就行了，所以我們可以簡單分析一些性質讓我們維護盡可能少的值。
ZR2463
設質數 \(p,q\)，若 \(x=pq\)，那么 \(n=pq-(p-1)(q-1)\Rightarrow n+1=pq\)，而 \(n+1\) 是一個偶數，根據哥德巴赫猜想，我們一定能夠找到一個 \(p\) 和一個 \(q\) 滿足條件，并且，實踐證明，較小的那個質數不會很大。
ZR2462
其實這種題目和哈夫曼樹半點關系沒有，但是我被嚇傻了。
首先顯然有一個樹的結構，而根節點的每個兒子把所有的點劃分成了若干區間，這就提示我們區間 DP。
設 \(f_{l,r,k}\) 表示把 \(l,r\) 這一段分成 \(k\) 段，每段代表一個子樹，目前來說還是一個森林的貢獻，\(ans_{l,r}\) 表示把 \(l,r\) 合并成一棵樹的貢獻，轉移只需要枚舉最后一段是哪一段即可，而 \(ans_{l,r}\) 就等于把 \(l,r\) 分成若干段，最后加一遍 \(l,r\) 每個點的頻率即可。
容易發現如果一個點所有的子節點不都是兒子，那么這個點一定有 \(K\) 個兒子，這樣才能滿足最優。所以我們相當于是只需要知道最后 \(f_{l,r,K}\) 的值，所以我們只需要知道 \(f_{l,r,i}\) 表示把區間分成 \(2^i\) 段的值，然后類似的再設一個狀態，把 \(K\) 二進制拆分，用來得到 \(f_{l,r,K}\) 的值即可。
實現細節較多。
#include<bits/stdc++.h>
#define mset(a,b) memset((a),(b),sizeof((a)))
#define rep(i,l,r) for(int i=(l);i<=(r);i++)
#define dec(i,l,r) for(int i=(r);i>=(l);i--)
#define cmax(a,b) (((a)<(b))?(a=b):(a))
#define cmin(a,b) (((a)>(b))?(a=b):(a))
#define Next(k) for(int x=head[k];x;x=li[x].next)
#define vc vector
#define ar array
#define pi pair
#define fi first
#define se second
#define mp make_pair
#define pb emplace_back
#define N 510
#define M number
using namespace std;
typedef double dd;
typedef long double ld;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
#define int long long
typedef pair<int,int> P;
typedef vector<int> vi;
const int INF=1e18;
const dd eps=1e-9;
template<typename T> inline void read(T &x) {
x=0; int f=1;
char c=getchar();
for(;!isdigit(c);c=getchar()) if(c == '-') f=-f;
for(;isdigit(c);c=getchar()) x=x*10+c-'0';
x*=f;
}
int n,K,a[N],f[N][N][6],ans[N][N],lg2[N],g[N][N][6],dk[6],sp;
signed main(){
// freopen("my.in","r",stdin);
// freopen("my.out","w",stdout);
read(n);read(K);rep(i,1,n) read(a[i]);
rep(i,0,5) dk[i]=-1;
rep(i,0,5) dec(j,0,i) if((K>>j)&1){
dk[i]=j;break;
}
// rep(i,0,5){
// printf("dk[%d]=%d\n",i,dk[i]);
// }
lg2[0]=-1;rep(i,1,K) lg2[i]=lg2[i>>1]+1;
sp=lg2[K&(-K)];
// printf("sp=%d\n",sp);
rep(i,1,n){
f[i][i][0]=0;ans[i][i]=0;
rep(j,1,5) f[i][i][j]=INF;
}
rep(i,2,n){
rep(j,1,n-i+1){
int l=j,r=j+i-1;
int len=r-l+1;
rep(k,0,5) f[l][r][k]=INF,g[l][r][k]=INF;
rep(o,1,5)if(len>=(1<<o)){
rep(k,l,r) f[l][r][o]=min(f[l][r][o],f[l][k][o-1]+f[k+1][r][o-1]);
}
rep(o,0,5){
if(dk[o]==-1){
g[l][r][o]=INF;
continue;
}
if(dk[o]==sp){
g[l][r][o]=f[l][r][dk[o]];
}
else{
rep(k,l,r){
g[l][r][o]=min(g[l][r][o],g[l][k][dk[o]-1]+f[k+1][r][dk[o]]);
}
}
}
// printf("g[1][4][1]=%d\n",g[1][4][1]);
if(len<=K){
rep(k,l,r) ans[l][r]+=a[k];
f[l][r][0]=ans[l][r];
rep(o,0,5) if(dk[o]==0) g[l][r][o]=ans[l][r];
}
else{
ans[l][r]=g[l][r][5];
rep(k,l,r) ans[l][r]+=a[k];
f[l][r][0]=ans[l][r];
rep(o,0,5) if(dk[o]==0) g[l][r][o]=ans[l][r];
}
// rep(o,0,5){
// printf("f[%lld][%lld][%lld]=%lld\n",l,r,o,f[l][r][o]);
// printf("g[%lld][%lld][%lld]=%lld\n",l,r,o,g[l][r][o]);
// }
}
}
printf("%lld\n",ans[1][n]);
return 0;
}
ZR2464
考慮這樣奇怪的數據范圍一定是折半搜索，我們考慮先分成兩半。又有一個轉化：\([2|c]\Leftrightarrow\frac{1+(-1)^c}{2}\)，這提示我們可以把一個點集的貢獻記為 \(-1\) 的這個點集的導出子圖的邊集大小次方。
考慮貢獻分為三部分，左邊集合，右邊集合，左右集合之間的邊。
固定一個左邊集合，對于右邊集合中的每一個點，如果這個點到左邊集合的邊數量為偶數，那么等價于這些邊都不存在，所以我們只需要關注那些到左邊集合邊數為奇數的右邊集合的點，設 \(\varphi(S)\) 表示對于一個左邊集合 \(S\)，右邊滿足上述條件的點的集合。
考慮如果直接枚舉左右兩邊集合，復雜度不會減少，不如對于右邊集合預處理一個 \(f_T\) 表示所有 \(\varphi(S)=T\) 的集合 \(S\) 的貢獻之和，設 \(g_T\) 為右邊集合 \(T\) 的貢獻，那么答案為：
\[\sum\limits_{A,B}f_Ag_B(-1)^{|A\cap B|}
\]
容易發現對于每個 \(A\) 來說，\(g_B(-1)^{|A\cap B|}\) 的形式恰好是一個異或卷積，所以 FWT 就做完了。
#include<bits/stdc++.h>
#define mset(a,b) memset((a),(b),sizeof((a)))
#define rep(i,l,r) for(int i=(l);i<=(r);i++)
#define dec(i,l,r) for(int i=(r);i>=(l);i--)
#define cmax(a,b) (((a)<(b))?(a=b):(a))
#define cmin(a,b) (((a)>(b))?(a=b):(a))
#define Next(k) for(int x=head[k];x;x=li[x].next)
#define vc vector
#define ar array
#define pi pair
#define fi first
#define se second
#define mp make_pair
#define pb emplace_back
#define N 50
#define M 23
using namespace std;
typedef double dd;
typedef long double ld;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
#define int long long
typedef pair<int,int> P;
typedef vector<int> vi;
const int INF=0x3f3f3f3f;
const dd eps=1e-9;
const int mod=998244353;
template<typename T> inline void read(T &x) {
x=0; int f=1;
char c=getchar();
for(;!isdigit(c);c=getchar()) if(c == '-') f=-f;
for(;isdigit(c);c=getchar()) x=x*10+c-'0';
x*=f;
}
int B,e[N],n,m,f[1ll<<M],g[1ll<<M],bit[1ll<<M],h[1ll<<M];
unordered_map<ll,int> lg2;
inline void FWTxor(int *f,int n){
for(int mid=1;mid<=(n>>1);mid<<=1)
for(int l=0;l<n;l+=(mid<<1))
for(int i=l;i<=l+mid-1;i++){
int a=f[i],b=f[i+mid];
f[i]=(a+b)%mod;f[i+mid]=(a-b)%mod;
}
}
inline int ksm(int a,int b,int mod){
int res=1;while(b){if(b&1)res=1ll*res*a%mod;a=1ll*a*a%mod;b>>=1;}return res;
}
inline int inv(int x){return ksm(x,mod-2,mod);}
signed main(){
// freopen("my.in","r",stdin);
// freopen("my.out","w",stdout);
read(n);read(m);
rep(i,1,m){
int u,v;read(u);read(v);
e[u]|=(1ll<<(v-1));
e[v]|=(1ll<<(u-1));
}
// rep(i,1,n){
// printf("i=%d e[i]=%d\n",i,e[i]);
// }
// lg2[0]=-1;
B=n/2;
rep(i,0,(1ll<<(max(B,n-B)))-1) bit[i]=bit[i>>1]^(i&1);
rep(i,0,n) lg2[1ll<<i]=i;
// rep(i,1,(1ll<<(max(B,n-B)))-1) lg2[i]=lg2[i>>1]+1;
rep(i,0,(1ll<<B)-1){
h[i]=h[i^(i&(-i))]^bit[e[lg2[i&(-i)]+1]&i];
// assert((e[lg2[i&(-i)]+1]&i)<=(1ll<<(max(B,n-B)))-1);
// printf("h[%d]=%lld\n",i,h[i]);
int now=0;
rep(j,B+1,n){
if(bit[e[j]&i]){
// assert((e[j]&i)<=(1ll<<(max(B,n-B)))-1);
now|=(1ll<<(j-B-1));
}
}
// printf("i=%d now=%d\n",i,now);
if(h[i]) f[now]--;
else f[now]++;
}
// printf("lg2[1]=%d\n",lg2[1]);
rep(i,0,(1ll<<(n-B))-1){
h[i]=0;
if(!i){
g[0]=1;
continue;
}
h[i]=h[i^(i&(-i))]^bit[(e[lg2[i&(-i)]+B+1]&(i<<(B)))>>B];
// assert(((e[lg2[i&(-i)]+B+1]&(i<<(B)))>>B)<=(1ll<<(max(B,n-B)))-1);
// printf("i=%lld i&(-i)=%lld,val=%lld,e[lg2[i&(-i)]+B+1]=%d\n",i,i&(-i),lg2[i&(-i)]+B+1,e[lg2[i&(-i)]+B+1]);
if(h[i]) g[i]--;
else g[i]++;
}
// exit(0);
rep(i,0,(1ll<<(n-B))-1){
// printf("f[%lld]=%lld\n",i,f[i]);
// printf("g[%lld]=%lld\n",i,g[i]);
f[i]%=mod;
g[i]%=mod;
}
FWTxor(g,1ll<<(n-B));
rep(i,0,(1ll<<(n-B))-1) f[i]=f[i]*g[i]%mod;
int ans=0;
rep(i,0,(1ll<<(n-B))-1) ans=(ans+f[i])%mod;
// printf("ans=%lld\n",ans);
(ans+=((1ll<<(n))%mod))%=mod;
ans=ans*inv(2)%mod;
printf("%lld\n",ans);
return 0;
}
ZR2447
考慮若小于等于 \(12\) 可以直接枚舉最小表示，否則，我們拿出 dfs 樹出來，那么把所有返祖邊的祖先節點弄為特殊點，先枚舉所有祖先節點的最小表示，然后可以設 DP \(f_{k,c}\) 表示 \(k\) 的顏色是 \(c\)，因為枚舉最小表示，所以 \(c\) 一定是小于等于 \(11\) 的，可以跑過去。
因為自己實現的太丑以至于調不出來，這里來一份別人的簡單易懂代碼。
#include<cstdio>
using namespace std;
const int o=210,MOD=1e9+7;
int T,n,m,K,h[o],cnt,mp[o][o],dif[o],sam[o],coef[o],col[o],d[o],f[o][o],g[o],b[o],tot,asd,ans;bool tr[o],sp[o];
struct Edge{int v,p,id;}e[o];
inline void ad(int U,int V,int ID){e[++cnt].v=V;e[cnt].p=h[U];e[h[U]=cnt].id=ID;}
void Dfs(int nw,int fa){
d[nw]=d[fa]+1;
for(int i=h[nw];i;i=e[i].p) if(e[i].v^fa)
if(d[e[i].v]>d[nw]) sp[nw]=1;
else if(!d[e[i].v]) tr[i]=1,d[e[i].v]=d[nw]+1,Dfs(e[i].v,nw);
if(sp[nw]) b[++tot]=nw;
}
void dfs(int nw,int fa){
for(int i=0;i<=asd;++i) f[nw][i]=(col[nw]==i||!sp[nw]);
for(int i=h[nw];i;i=e[i].p) if(e[i].v^fa)
if(!tr[i]){if(d[nw]>d[e[i].v]) for(int j=0;j<=asd;++j) f[nw][j]=f[nw][j]*1ll*(col[e[i].v]==j?sam[e[i].id]:dif[e[i].id])%MOD;}
else{
dfs(e[i].v,nw);
for(int j=0;j<=asd;++j) f[nw][j]=((g[e[i].v]+MOD-f[e[i].v][j])*1ll*dif[e[i].id]+f[e[i].v][j]*1ll*sam[e[i].id])%MOD*f[nw][j]%MOD;
}
g[nw]=f[nw][0]*1ll*(K-asd)%MOD;
for(int i=1;i<=asd;++i) g[nw]=(g[nw]+f[nw][i])%MOD;
}
void ddfs(int nw){
if(nw>tot){dfs(1,0);ans=(ans+coef[asd]*1ll*g[1])%MOD;return;}
for(int i=1;i<=asd;++i) col[b[nw]]=i,ddfs(nw+1);
col[b[nw]]=++asd;ddfs(nw+1);--asd;
}
int main(){
for(scanf("%d",&T);T--;printf("%d\n",ans),ans=cnt=tot=0){
scanf("%d%d%d",&n,&m,&K);
for(int i=1;i<=n;++i) h[i]=d[i]=col[i]=0;
for(int i=1;i<=2*m;++i) tr[i]=sp[i]=0;
for(int i=1;i<=n;++i) for(int j=1;j<=n;++j) mp[i][j]=0;
for(int i=1,u,v,a,b;i<=m;++i){
scanf("%d%d%d%d",&u,&v,&a,&b);
if(!mp[u][v]) dif[i]=a,sam[i]=b,mp[u][v]=mp[v][u]=i,ad(u,v,i),ad(v,u,i);
else dif[mp[u][v]]=dif[mp[u][v]]*1ll*a%MOD,sam[mp[u][v]]=sam[mp[u][v]]*1ll*b%MOD;
}
for(int i=coef[0]=1;i<=n;++i) coef[i]=coef[i-1]*(K-i+1ll)%MOD;
Dfs(1,0);ddfs(1);
}
return 0;
}
浙公網安備 33010602011771號