1. 1229A Marcin and Training Camp
大意: 给定$n$个对$(a_i,b_i)$, 要求选出一个集合, 使得不存在一个元素好于集合中其他所有元素. 若$a_i$的二进制中某一位为$1$, $a_j$对应位为$0$, 那么$(a_i,b_i)$好于$(a_j,b_j)$.
显然出现次数不少于$2$的数都可以选, 然后再把包含关系的数全选了即可.
#include <iostream>
#include <sstream>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <set>
#include <map>
#include <queue>
#include <string>
#include <cstring>
#include <bitset>
#include <functional>
#include <random>
#define REP(i,a,n) for(int i=a;i<=n;++i)
#define PER(i,a,n) for(int i=n;i>=a;--i)
#define hr putchar(10)
#define pb push_back
#define lc (o<<1)
#define rc (lc|1)
#define mid ((l+r)>>1)
#define ls lc,l,mid
#define rs rc,mid+1,r
#define x first
#define y second
#define io std::ios::sync_with_stdio(false)
#define endl '\n'
#define DB(a) ({REP(__i,1,n) cout<<a[__i]<<',';hr;})
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int P = 1e9+7, INF = 0x3f3f3f3f;
ll gcd(ll a,ll b) {return b?gcd(b,a%b):a;}
ll qpow(ll a,ll n) {ll r=1%P;for (a%=P;n;a=a*a%P,n>>=1)if(n&1)r=r*a%P;return r;}
ll inv(ll x){return x<=1?1:inv(P%x)*(P-P/x)%P;}
inline int rd() {int x=0;char p=getchar();while(p<'0'||p>'9')p=getchar();while(p>='0'&&p<='9')x=x*10+p-'0',p=getchar();return x;}
//head const int N = 1e6+50;
int n;
struct _ {
ll a;
int b;
} f[N];
map<ll,int> s; int main() {
scanf("%d", &n);
REP(i,1,n) {
scanf("%lld",&f[i].a);
++s[f[i].a];
}
REP(i,1,n) f[i].b=rd();
ll ans = 0;
set<int> ss;
for (auto t:s) if (t.y>=2) {
ll ret = 0;
REP(i,1,n) {
if ((f[i].a|t.x)==t.x) ss.insert(i);
}
}
for(auto t:ss) ans+=f[t].b;
printf("%lld\n",ans);
}
2. 1229B Kamil and Making a Stream
大意: 给定树, 给定每个节点的点权, 定义$f(u,v)$表示$u$到$v$路径的$gcd$
求$\sum\limits_{\text{u is an ancestor of v}}f(u,v)$.
每个点往上走的gcd种类数是$O(log)$的, 直接对每个点维护一个map<ll,int>就行了.
这种题CF早就出烂了, 昨天晚上不知道在想啥, 硬是写了个可撤销链表, 改到最后搞的C题也没时间看了
#include <iostream>
#include <sstream>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <set>
#include <map>
#include <queue>
#include <string>
#include <cstring>
#include <bitset>
#include <functional>
#include <random>
#define REP(i,a,n) for(int i=a;i<=n;++i)
#define PER(i,a,n) for(int i=n;i>=a;--i)
#define hr putchar(10)
#define pb push_back
#define lc (o<<1)
#define rc (lc|1)
#define mid ((l+r)>>1)
#define ls lc,l,mid
#define rs rc,mid+1,r
#define x first
#define y second
#define io std::ios::sync_with_stdio(false)
#define endl '\n'
#define DB(a) ({REP(__i,1,n) cout<<a[__i]<<',';hr;})
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int P = 1e9+7, INF = 0x3f3f3f3f;
ll gcd(ll a,ll b) {return b?gcd(b,a%b):a;}
ll qpow(ll a,ll n) {ll r=1%P;for (a%=P;n;a=a*a%P,n>>=1)if(n&1)r=r*a%P;return r;}
ll inv(ll x){return x<=1?1:inv(P%x)*(P-P/x)%P;}
inline int rd() {int x=0;char p=getchar();while(p<'0'||p>'9')p=getchar();while(p>='0'&&p<='9')x=x*10+p-'0',p=getchar();return x;}
//head const int N = 1e6+50;
int n;
ll a[N];
vector<int> g[N];
map<ll,int> mp[N];
int ans; void dfs(int x, int f) {
for (auto t:mp[f]) mp[x][gcd(t.x,a[x])]+=t.y;
++mp[x][a[x]];
for (auto t:mp[x]) ans=(ans+t.x*t.y)%P;
for (int y:g[x]) if (y!=f) dfs(y,x);
} int main() {
scanf("%d", &n);
REP(i,1,n) scanf("%lld",a+i);
REP(i,2,n) {
int u, v;
scanf("%d%d",&u,&v);
g[u].pb(v),g[v].pb(u);
}
dfs(1,0);
printf("%d\n", ans);
}
3. 1229C Konrad and Company Evaluation
大意: 给定一个有向图, 每条边方向为编号大的点指向编号小的点, 给定$q$次操作, 每次操作给出$x$, 将$x$所有入边换成出边, 求所有三元组$(i,j,k)$的个数, 满足$(i,j)$间有一条边, $(j,k)$间有一条边.
建出反向图直接暴力, 复杂度是$O(m+q\sqrt{m})$, 证明考虑势能分析.
按度数从小到大排序, 定义势函数为所有从左指向右的边数.
每次修改一个点$x$, 那么要遍历$x$的所有入边, 把入边全部改为出边.
假设入边中有$A$条指向右, $B$条入边指向左, 那么
$\Delta \phi = B-A, C_{actual}=A+B$
$C_{amortized}=C_{actual}+\Delta \phi = 2B = O(\sqrt{m})$
$\sum\limits_{i=1}^q C_{actual}=\phi(0)+qO(\sqrt{m})=O(m+q\sqrt{m})$
#include <iostream>
#include <sstream>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <set>
#include <map>
#include <queue>
#include <string>
#include <cstring>
#include <bitset>
#include <functional>
#include <random>
#define REP(i,a,n) for(int i=a;i<=n;++i)
#define PER(i,a,n) for(int i=n;i>=a;--i)
#define hr putchar(10)
#define pb push_back
#define lc (o<<1)
#define rc (lc|1)
#define mid ((l+r)>>1)
#define ls lc,l,mid
#define rs rc,mid+1,r
#define x first
#define y second
#define io std::ios::sync_with_stdio(false)
#define endl '\n'
#define DB(a) ({REP(__i,1,n) cout<<a[__i]<<',';hr;})
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int P = 1e9+7, INF = 0x3f3f3f3f;
ll gcd(ll a,ll b) {return b?gcd(b,a%b):a;}
ll qpow(ll a,ll n) {ll r=1%P;for (a%=P;n;a=a*a%P,n>>=1)if(n&1)r=r*a%P;return r;}
ll inv(ll x){return x<=1?1:inv(P%x)*(P-P/x)%P;}
inline int rd() {int x=0;char p=getchar();while(p<'0'||p>'9')p=getchar();while(p>='0'&&p<='9')x=x*10+p-'0',p=getchar();return x;}
//head const int N = 1e6+50;
int n, m, in[N], out[N];
vector<int> g[N]; int main() {
scanf("%d%d", &n, &m);
REP(i,1,m) {
int u, v;
scanf("%d%d", &u, &v);
if (u>v) swap(u,v);
++out[v],++in[u];
g[u].pb(v);
}
ll ans = 0;
REP(i,1,n) ans+=(ll)in[i]*out[i];
printf("%lld\n", ans);
int q;
scanf("%d", &q);
while (q--) {
int x;
scanf("%d", &x);
ans -= (ll)in[x]*out[x];
for (int y:g[x]) {
--out[y];
ans += out[y]-in[y];
++in[y];
g[y].pb(x);
}
out[x]+=in[x],in[x]=0;
g[x].clear();
printf("%lld\n", ans);
}
}
4. 1229D Wojtek and Card Tricks
大意: 给定$n$个$k$排列, 定义$f(l,r)$为任选区间$[l,r]$的排列相乘能得到的不同排列数, 每个排列可以选多次, 可以按任意顺序相乘. 求$\sum\limits_{i=1}^n\sum\limits_{j=i}^nf(i,j)$
枚举右端点, 维护每个左端点对应答案, 维护每种排列最后出现位置.
问题就转化为维护一个排列的集合, 要求支持插入一个排列, 询问当前集合能表示的不同排列数.
根据抽象代数的一些理论, 对于添加一个新排列$v$, 若$v$已经能表示出来, 那么答案不变, 否则答案至少变为$2$倍.
这样维护$O(\log{k!})$个基底, 每次暴力更新即可. 复杂度为$O(nk!k)$
#include <iostream>
#include <sstream>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <set>
#include <map>
#include <queue>
#include <string>
#include <cstring>
#include <bitset>
#include <functional>
#include <random>
#define REP(i,a,n) for(int i=a;i<=n;++i)
#define PER(i,a,n) for(int i=n;i>=a;--i)
#define hr putchar(10)
#define pb push_back
#define lc (o<<1)
#define rc (lc|1)
#define mid ((l+r)>>1)
#define ls lc,l,mid
#define rs rc,mid+1,r
#define x first
#define y second
#define io std::ios::sync_with_stdio(false)
#define endl '\n'
#define DB(a) ({REP(__i,1,n) cout<<a[__i]<<',';hr;})
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int P = 1e9+7, INF = 0x3f3f3f3f;
ll gcd(ll a,ll b) {return b?gcd(b,a%b):a;}
ll qpow(ll a,ll n) {ll r=1%P;for (a%=P;n;a=a*a%P,n>>=1)if(n&1)r=r*a%P;return r;}
ll inv(ll x){return x<=1?1:inv(P%x)*(P-P/x)%P;}
inline int rd() {int x=0;char p=getchar();while(p<'0'||p>'9')p=getchar();while(p>='0'&&p<='9')x=x*10+p-'0',p=getchar();return x;}
//head const int N = 1e6+50;
int n, k;
vector<int> g[N];
int top, s[N], vis[N];
map<vector<int>,int> ID;
vector<int> a[122], bas;
int ff[122][122], arr[N]; vector<int> mul(const vector<int> &a, const vector<int> &b) {
int n = a.size();
vector<int> ret(n);
for (int i=0; i<n; ++i) ret[i]=a[b[i]];
return ret;
} bitset<122> bit;
void ins(int x) {
if (bit[x]) return;
bit[x] = 1;
for (auto &t:bas) ins(ff[x][t]);
} const int fac[]={1,1,2,6,24,120};
int Hash(const vector<int> &v) {
int r = 0, n = v.size();
REP(i,1,n-1) {
int t = 0;
REP(j,0,i-1) if (v[j]>v[i]) ++t;
r += t*fac[i];
}
return r;
} int main() {
scanf("%d%d", &n, &k);
vector<int> d(k);
REP(i,0,k-1) d[i] = i;
int tot = 0;
do {
a[Hash(d)] = d, ++tot;
} while (next_permutation(d.begin(),d.end()));
REP(i,0,tot-1) REP(j,0,tot-1) ff[i][j] = Hash(mul(a[i],a[j]));
REP(i,1,n) {
vector<int> v(k);
for (auto &t:v) scanf("%d",&t),--t;
arr[i] = Hash(v);
}
ll ans = 0;
REP(i,1,n) {
vis[arr[i]] = i;
top = 0;
REP(j,0,tot-1) if (vis[j]) s[++top]=vis[j];
sort(s+1,s+1+top,greater<int>());
s[++top] = 0;
bit.reset();
bas.clear();
REP(i,1,top-1) {
int id = arr[s[i]];
if (!bit[id]) bas.pb(id), ins(id);
ans += bit.count()*(s[i]-s[i+1]);
}
}
printf("%lld\n", ans);
}
5. 1229E1 Marek and Matching (easy version)
大意: 给定一个二分图, 边$(l_i,r_j)$出现概率为$p_{ij}$, 求完美匹配的概率.
考虑折半搜索, 求出$L$和$R_1,R_2,R_3$匹配的概率, 以及$L$和$R_4,R_5,R_6$匹配的概率.
一共只有$18$条边, 直接暴力枚举可以在$O(2^{18})$的时间求出
然后注意到有效状态只有$\binom{6}{3}=20$, 可以用一个20位二进制表示
设$p_1(A)$表示对于$R_1,R_2,R_3$匹配到某一个状态, 能使$R_4,R_5,R_6$再匹配到状态$A$的概率, $p_2(B)$表示$R_4,R_5,R_6$匹配到状态$B$的概率.
那么不能完美匹配的概率就为$\sum\limits_{A\cap B=\varnothing}p_1(A)p_2(B)$
直接暴力求是$O(3^{20})$, 可以先求出$f(S)=\sum\limits_{A\in S} p_1(A)$, 转化为求$\sum f(S)p_2(2^{20}-1-S)$, 这样复杂度就为$O(2^{20}\cdot 20)$
#include <iostream>
#include <sstream>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <set>
#include <map>
#include <queue>
#include <string>
#include <cstring>
#include <bitset>
#include <functional>
#include <random>
#define REP(i,a,n) for(int i=a;i<=n;++i)
#define PER(i,a,n) for(int i=n;i>=a;--i)
#define hr putchar(10)
#define pb push_back
#define lc (o<<1)
#define rc (lc|1)
#define mid ((l+r)>>1)
#define ls lc,l,mid
#define rs rc,mid+1,r
#define x first
#define y second
#define io std::ios::sync_with_stdio(false)
#define endl '\n'
#define DB(a) ({REP(__i,1,n) cout<<a[__i]<<',';hr;})
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int P = 1e9+7, INF = 0x3f3f3f3f;
ll gcd(ll a,ll b) {return b?gcd(b,a%b):a;}
ll qpow(ll a,ll n) {ll r=1%P;for (a%=P;n;a=a*a%P,n>>=1)if(n&1)r=r*a%P;return r;}
ll inv(ll x){return x<=1?1:inv(P%x)*(P-P/x)%P;}
inline int rd() {int x=0;char p=getchar();while(p<'0'||p>'9')p=getchar();while(p>='0'&&p<='9')x=x*10+p-'0',p=getchar();return x;}
//head const int N = 10, M = (1<<20)-1;
int n, ans, a[N][N];
int g[N][N], ID[N][N][N];
int p[1<<20]; int chk(int x, int y, int z) {
if (g[1][x]&&g[2][y]&&g[3][z]) return 1;
if (g[1][x]&&g[2][z]&&g[3][y]) return 1;
if (g[1][y]&&g[2][x]&&g[3][z]) return 1;
if (g[1][y]&&g[2][z]&&g[3][x]) return 1;
if (g[1][z]&&g[2][x]&&g[3][y]) return 1;
if (g[1][z]&&g[2][y]&&g[3][x]) return 1;
return 0;
} void solve1(int ret, int x, int y) {
if (x==4) {
int s = 0;
REP(i,1,6) REP(j,i+1,6) REP(k,j+1,6) if (chk(i,j,k)) {
int x = 1;
while (x==i||x==j||x==k) ++x;
int y = x+1;
while (y==i||y==j||y==k) ++y;
int z = y+1;
while (z==i||z==j||z==k) ++z;
s ^= ID[x][y][z];
}
p[s] = (p[s]+ret)%P;
return;
}
g[x][y] = 1;
if (y==6) solve1((ll)ret*a[x][y]%P,x+1,1);
else solve1((ll)ret*a[x][y]%P,x,y+1);
g[x][y] = 0;
if (y==6) solve1((ll)ret*(1-a[x][y])%P,x+1,1);
else solve1((ll)ret*(1-a[x][y])%P,x,y+1);
} void solve2(int ret, int x, int y) {
if (x==7) {
int s = 0;
REP(i,1,6) REP(j,i+1,6) REP(k,j+1,6) if (chk(i,j,k)) s ^= ID[i][j][k];
ans = (ans+(ll)p[M^s]*ret)%P;
return;
}
g[x-3][y] = 1;
if (y==6) solve2((ll)ret*a[x][y]%P,x+1,1);
else solve2((ll)ret*a[x][y]%P,x,y+1);
g[x-3][y] = 0;
if (y==6) solve2((ll)ret*(1-a[x][y])%P,x+1,1);
else solve2((ll)ret*(1-a[x][y])%P,x,y+1);
} int main() {
scanf("%d", &n);
REP(i,1,n) REP(j,1,n) scanf("%d",a[i]+j),a[i][j]=(ll)a[i][j]*inv(100)%P;
REP(i,n+1,6) a[i][i] = 1;
int tot = 0;
REP(i,1,6) REP(j,i+1,6) REP(k,j+1,6) ID[i][j][k]=1<<tot++;
solve1(1,1,1);
REP(i,0,19) REP(j,0,M) if (j>>i&1) p[j]=(p[j]+p[j^1<<i])%P;
solve2(1,4,1);
ans = (1-ans)%P;
if (ans<0) ans += P;
printf("%d\n", ans);
}
6. 1229E2 Marek and Matching (hard version)
E1的加强版, $n$最大为$7$, 折半搜索复杂度高达$O(2^{35}\cdot 35)$, 需要考虑更优秀的做法.
定义一个$n$位二进制状态$S$表示$L$中的点的匹配情况(匹配到为$1$,否则为$0$), 考虑逐步添加$R$中的点, 因为每个点会连多条边, 一种连边情况可能会对应多种匹配情况.
再把所有可能的$S$状压一下, 用一个$128$位二进制数存, 第$S$位表示当前连边情况是否能构成匹配$S$. 打表所有可能的状态最多只有$64184$种, 预处理一下转移情况然后$dp$即可. 复杂度很玄学, 15s应该是稳够的.
#include <iostream>
#include <sstream>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <set>
#include <map>
#include <queue>
#include <string>
#include <cstring>
#include <bitset>
#include <functional>
#include <random>
#include <unordered_map>
#define REP(i,a,n) for(int i=a;i<=n;++i)
#define PER(i,a,n) for(int i=n;i>=a;--i)
#define hr putchar(10)
#define pb push_back
#define lc (o<<1)
#define rc (lc|1)
#define mid ((l+r)>>1)
#define ls lc,l,mid
#define rs rc,mid+1,r
#define x first
#define y second
#define io std::ios::sync_with_stdio(false)
#define endl '\n'
#define DB(a) ({REP(__i,1,n) cout<<a[__i]<<',';hr;})
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int P = 1e9+7, INF = 0x3f3f3f3f;
ll gcd(ll a,ll b) {return b?gcd(b,a%b):a;}
ll qpow(ll a,ll n) {ll r=1%P;for (a%=P;n;a=a*a%P,n>>=1)if(n&1)r=r*a%P;return r;}
ll inv(ll x){return x<=1?1:inv(P%x)*(P-P/x)%P;}
inline int rd() {int x=0;char p=getchar();while(p<'0'||p>'9')p=getchar();while(p>='0'&&p<='9')x=x*10+p-'0',p=getchar();return x;}
//head const int N = 70000; typedef bitset<128> bit;
int n,tot,mx,a[10][10];
unordered_map<bit,int> ID;
int trans[N][130],p[10][130];
int f[10][N]; //L的所有匹配情况有128种, 用128位二进制数记录
//trans[x][y] 表示128位的状态为x, R中新添的一个点连边状态为y时, 对应的128位状态
//
//考虑逐步添加R中的点
//f[x][y] 表示当前遍历到Rx, 对应128位状态为y的概率
// int dfs(bit s) {
if (ID.count(s)) return ID[s];
ID[s] = ++tot;
//枚举Rx的所有连边情况, i中为1的位表示Rx与L相连的位
REP(i,0,mx) {
bit t = s; //对于s中已经有的状态添加一个点后一定还有
REP(j,0,mx) if (!t[j]) {//依次考虑s中没有的状态
int w = i&j;
//枚举每一条边
while (w) {
int k = w&-w;
//如果s中可以匹配到j^k, 那么Rx与L中第Logk条边匹配即可达到状态j
if (s[j^k]) {t[j]=1;break;}
w ^= k;
}
}
trans[ID[s]][i] = dfs(t);
}
return ID[s];
}
void add(int &a, ll b) {a=(a+b)%P;} int main() {
scanf("%d", &n);
mx = (1<<n)-1;
REP(i,0,n-1) REP(j,0,n-1) scanf("%d",a[i]+j),a[i][j]=(ll)a[i][j]*inv(100)%P;
dfs(1); //预处理一下p[x][y], 表示Rx连边状态为y的概率
REP(i,0,n-1) REP(j,0,mx) {
int r = 1;
REP(k,0,n-1) {
if (j>>k&1) r=(ll)r*a[i][k]%P;
else r=(ll)r*(1-a[i][k])%P;
}
p[i][j] = r;
} f[0][1] = 1;
REP(i,0,n-1) REP(j,1,tot) {
REP(k,0,mx) {
//假设前i个点答案已经求出
//当前可以达到的128位匹配情况为j
//第i+1个点的连边情况为k
add(f[i+1][trans[j][k]],(ll)f[i][j]*p[i][k]);
}
} bit t;
REP(i,0,mx) t[i] = 1;
int ans = f[n][ID[t]];
if (ans<0) ans += P;
printf("%d\n", ans);
}
7. 1229F Mateusz and Escape Room
大意: 给定$n$元素的环, $i$位置有$a_i$个硬币, 每次操作可以把硬币移到相邻位置. 给定每个位置的限制$(l_i,r_i)$, 求最少操作次数使得$l_i\le a_i\le r_i$
dp优化实在不会..... 这题放弃了