A [* easy]
你有四块饼干，美味度分别为 (A, B, C, D)，问能否吃掉一些饼干使得吃掉饼干的美味度之和等于剩下饼干的美味度之和。
(1 le A, B, C, D le 10 ^ 8)
Solution
排个序，要么 (A=B+C+D) 要么 (A+D=B+C)
B [* easy]
给定 (n) 个数 (a_i)，然后执行以下操作：
- 令 (X) 表示其中的最大值，(x) 表示其中的最小值。
- 如果 (X=x)，那么终止操作，否则将所有 (a_i=X) 的 (a_i) 替换为 (X-x)
输出终止操作时 (a_1) 的权值。
(Nle 10^5,a_ile 10^9)
Solution
考虑操作的流程，每次选最小值 (t) 然后给所有数一直减少直到小于 (2t)
然后我们会更换这个最小值。
然后发现流程神似辗转相减，如果只有两个数显然 ans 是 (gcd)，因为他就是辗转相减。
然后可以猜 (n) 的时候就是 (n) 个数的 (gcd)，显然答案一定是他的倍数，不过具体论证我其实不会。
C [* easy]
有 (n) 只骆驼要过桥，第 (i) 只骆驼重量为 (w_i)。
桥分为 (m) 个部分，每个部分长度为 (l_i) 容重为 (v_i)。
你需要规定骆驼过桥的顺序和相邻两头骆驼之间的距离，使得桥不倒塌的情况下最小化第一只骆驼和最后一只骆驼之间的距离。
(2 le n le 8, 1 le m le 10 ^ 5, 1 le w_i, l_i, v_i le 10 ^8)
Solution
假设枚举一个排列，然后从后往前记前缀和，如果区间 ([l,r]) 的和大于 (w_i)，那么 (a_r-a_lge l_i)，这样连接一条 (l) 到 (r) 的边边权为 (l_i)，同时给 (l) 到 (l+1) 连一条 (0) 的边，这张图走到 (n) 的最长路即为答案。
注意到这张图是 DAG，所以最长路的求解是可以基于 dp 的。
将 (m) 提前排好序，然后查一下即可，复杂度 (mathcal O(n!cdot n^2log m))
(Code:)
#include<bits/stdc++.h>
using namespace std ;
#define Next( i, x ) for( register int i = head[x]; i; i = e[i].next )
#define rep( i, s, t ) for( register int i = (s); i <= (t); ++ i )
#define drep( i, s, t ) for( register int i = (t); i >= (s); -- i )
#define re register
#define int long long
int gi() {
char cc = getchar() ; int cn = 0, flus = 1 ;
while( cc < '0' || cc > '9' ) { if( cc == '-' ) flus = - flus ; cc = getchar() ; }
while( cc >= '0' && cc <= '9' ) cn = cn * 10 + cc - '0', cc = getchar() ;
return cn * flus ;
}
const int inf = 1e15 + 5 ;
const int N = 10 ;
const int M = 1e5 + 5 ;
int n, w[N], Id[N], b[N], f[N], m ;
struct node {
int l, v ;
node(int _l = 0, int _v = 0) { l = _l, v = _v ; }
bool operator < ( const node &x ) const {
return (l == x.l) ? v > x.v : l < x.l ;
}
} l[M] ;
set<node> S ;
set<node>::iterator it ;
signed main()
{
n = gi(), m = gi() ; int mx = 0, mi = inf ;
rep( i, 1, n ) w[i] = gi(), Id[i] = i, mx = max(mx, w[i]) ;
rep( i, 1, m ) l[i].v = gi(), l[i].l = gi(), mi = min( mi, l[i].l ) ;
if( mx > mi ) { puts("-1") ; exit(0) ; }
sort(l + 1, l + m + 1) ;
S.insert(node(-1, 0)), S.insert(l[1]) ;
rep( i, 2, m ) l[i].v = max( l[i - 1].v, l[i].v ) ;
rep( i, 2, m ) S.insert(l[i]) ;
int Ans = inf ;
do {
b[0] = 0 ;
rep( i, 1, n ) b[i] = w[Id[i]] ;
rep( i, 1, n ) b[i] += b[i - 1] ;
rep( i, 1, n ) f[i] = 0 ;
rep( i, 2, n ) {
f[i] = f[i - 1] ;
rep( j, 1, i - 1 ) {
it = S.upper_bound(node(b[i] - b[j - 1], inf)) ;
-- it ; node u = *it ;
f[i] = max( f[i], f[j] + u.v ) ;
}
}
Ans = min( Ans, f[n] ) ;
} while(next_permutation(Id + 1, Id + n + 1)) ;
cout << Ans << endl ;
return 0 ;
}
D [* easy]
给定 (N) 个背包，第 (i) 个背包有 (a_i) 个硬币。初始有 (N) 个空盘子。
- 当至少有一个背包不为空的时候，你可以将一个背包的所有硬币移动到一个空盘子上。
- 当所有背包都为空的时候，你可以选择一个非空盘子，然后将其中至少一个硬币移走。
无法操作者输，(T) 组数据，判定每组数据先手和后手谁必胜。
(Tle 10^5,Nle 10^5,1le a_ile 10^9,sum Nle 2 imes 10^5)
Solution
第二个操作是 Nim，然后我们假设有奇数个背包，那么接下来将为后手先手。
不妨先考虑偶数个背包的情况，先手接下来仍然是先手，他希望异或和不为 (0)，后手希望异或和为 (0)
于是先手的策略应该为将数字累加在一起，显然此策略在元素不满足两两成对出现时均能够获得胜利，否则均会获得失败。（此时可以后手对称操作）
然后考虑奇数个背包的情况，此时先手希望异或和为 (0)，无论先手初始如何操作，后手都将剩余最大值累到先手的位置上，显然先手失败。
(Code:)
#include<bits/stdc++.h>
using namespace std ;
#define Next( i, x ) for( register int i = head[x]; i; i = e[i].next )
#define rep( i, s, t ) for( register int i = (s); i <= (t); ++ i )
#define drep( i, s, t ) for( register int i = (t); i >= (s); -- i )
#define re register
#define int long long
int gi() {
char cc = getchar() ; int cn = 0, flus = 1 ;
while( cc < '0' || cc > '9' ) { if( cc == '-' ) flus = - flus ; cc = getchar() ; }
while( cc >= '0' && cc <= '9' ) cn = cn * 10 + cc - '0', cc = getchar() ;
return cn * flus ;
}
const int N = 1e5 + 5 ;
int n, a[N] ;
signed main()
{
int T = gi() ;
while( T-- ) {
n = gi() ;
rep( i, 1, n ) a[i] = gi() ;
if( n & 1 ) puts("Second") ;
else {
int flag = 0 ;
sort(a + 1, a + n + 1) ;
for(re int i = 1; i < n; i += 2 )
if( a[i] != a[i + 1] ) flag = 1 ;
if( flag ) puts("First") ;
else puts("Second") ;
}
rep( i, 1, n ) a[i] = 0 ;
}
return 0 ;
}
E [* easy]
定义一张无向图为好的，当且仅当 (1) 号点和 (n) 号点不连通且图中不存在自环和重边。
初始给定一张 (n) 个点 (m) 条边的好图 (G)，现在有两个人在这张图上轮流博弈。
每次操作可以选择两个点 (u, v) 并连接这两个点，最终无论如何操作都不能继续使得 (G) 依然是好图的玩家失败。
问是先手必胜还是后手必胜，多组查询。
(T le 10^5, sum n le 2cdot 10^5, sum m le 2cdot 10^5)
Solution
最终的连边必然会使得图分成两部分，因为两个人都要操作，然后我们加入的边数也固定为 (inom{x}{2}+inom{y}{2}-m)。
设 (t) 表示这个值，显然 (t) 为奇数先手胜，(t) 为偶数后手胜，同时我们可以将连通连通块操作提前，因为无论先手还是后手来进行连通连通块，答案都是一样的（对于最终局面，显然这些边都是可以操作的，时间无关，同时如果不操作可能会使得另一方提前达到想要的局面）
问题可以简化为给定若干个数 (a_i)，然后 (a_1) 不能与 (a_n) 合并，每次可以合并两个数，设 (t) 为 (inom{x}{2}+inom{n-x}{2}) 如果 (m) 为偶数，那么先手希望 (t) 为奇数，后手希望为偶数，求先手后手谁必败（奇数反之）。
然后这样还是很麻烦，考虑进一步转换，注意到奇偶性下 (t) 等价于 (inom{n}{2}-x(n-x))，那么只需要考虑 (x(n-x)) 的奇偶性，先手希望其奇数等价于 (x) 和 ((n-x)) 都是奇数，所以 (n) 为奇数希望奇数的那个必然输，否则 (n) 为偶数，那么能够改变答案的只有大小为奇数的连通块，假设有 (t) 个，然后偶数有 (k) 个，基于观察我们发现操作仅有两种：
- 将两个奇数消去，得到一个偶数。
- 将奇数和 (a_1/a_n) 联通。
- 删除一个偶数。
我们发现假设先手可以取到最后一个奇数，那么先手 win，此时奇数个数一定是奇数，且先手一定可以 win。
假设奇数个数为偶数，那么不难发现先手可以保证后手无法取到最后一个奇数（通过操作 (1)）考虑 (t) 为偶数，显然 (t=2) 无法，(t=4) 的时候，如果先手操作了 (1)，那么后手一定能取到至少一个 (1)，然后变成 (t=2) 的局面，所以先手只能转为 (t=2) 的局面，假设 (t=6)，那么先手操作后仍只有变成 (t=4) 的局面，操作 (1) 个与 (t=4) 类似，归纳即可。
所以此时奇数无用，只需要讨论一下 (1) 号节点在的连通块的大小即可。
(Code:)
#include<bits/stdc++.h>
using namespace std ;
#define Next( i, x ) for( register int i = head[x]; i; i = e[i].next )
#define rep( i, s, t ) for( register int i = (s); i <= (t); ++ i )
#define drep( i, s, t ) for( register int i = (t); i >= (s); -- i )
#define re register
#define vi vector<int>
#define pb push_back
#define int long long
int gi() {
char cc = getchar() ; int cn = 0, flus = 1 ;
while( cc < '0' || cc > '9' ) { if( cc == '-' ) flus = - flus ; cc = getchar() ; }
while( cc >= '0' && cc <= '9' ) cn = cn * 10 + cc - '0', cc = getchar() ;
return cn * flus ;
}
const int N = 2e5 + 5 ;
int n, m, t, k, f, vis[N] ;
vi G[N] ;
void dfs(int x) {
vis[x] = 1 ;
for(int v : G[x]) if(!vis[v]) dfs(v), vis[x] += vis[v] ;
}
void solve() {
n = gi(), m = gi() ; int x, y ;
rep( i, 1, m ) x = gi(), y = gi(), G[x].pb(y), G[y].pb(x) ;
f = ((n * (n - 1) / 2 + m) & 1) ;
dfs(1), dfs(n) ;
rep( i, 1, n ) {
if(vis[i]) continue ;
dfs(i) ;
if( vis[i] & 1 ) ++ t ;
else ++ k ;
}
int u = (t & 1) ;
if(n & 1) {
if(f) puts("First") ;
else puts("Second") ;
}
else {
if(u) puts("First") ;
else if( !(f ^ (vis[1] & 1)) ) puts("Second") ;
else puts("First") ;
}
rep( i, 1, n ) G[i].clear(), vis[i] = 0 ; f = t = k = 0 ;
}
signed main()
{
int T = gi() ;
while( T-- ) solve() ;
return 0 ;
}
F [* easy]
给定一张 (N) 个点的无向图，以及 (M) 条边，保证图 (G) 联通且无自环无重边。起初所有边均为红色。
对于 (G) 一张边生成子图 (G')，定义其合法当且仅当：
- (G') 是联通的。
- 你可以执行以下操作使得原图所有边变成蓝色：
- 选择一个节点并翻转其所有出边的颜色。
(Nle 17,Min [N-1,frac{N(N-1)}{2}])
答案对 (998244353) 取模。
Solution
显然每个点只有两种状态：被操作过或者没被操作过，将这视为黑色和白色。
所以问题等价于每条边都需要连接一个黑色点和白色点，即图为二分图。
所以问题等价于无向图 (G) 的联通二分图生成子图计数问题。
考虑状压 dp，现在对于状态 (S) 我们希望计算其二分图生成子图数量，这样设 (p) 为其中编号最小的节点，然后我们枚举一个集合 (A) 和集合 (B) 满足 (Aland B=varnothing, Alor B=S)，这样 (A,B) 之间的边只需要使得其联通那么即为合法的状态。
仍然联通图计数也很困难，考虑直接统计 (2^{A o B}) 的和，那么显然有非法的二分图被计算入内。
我们考虑强制让 (pin A)，这样假设一个二分图有 (k) 个连通块，显然其会被计算 (2^{k-1}) 次。
我们希望将这 (2^{k-1}) 次全部减去。
仍然枚举一个 (A') 使得 (pin A')，那么此时我们计算 (A') 构成二分图的方案数，然后强制使得 (A') 和 (A'oplus S) 不连通，那么只需要考虑 (A'oplus S) 内部的方案，我们希望其中每种联通/不连通的方案都被计算 (2^{k}) 次，这样算上 (A') 相当于作为整体的连通块相当于被计算了 (2^{k-1}) 次。
显然这样可以不重不漏的将所有非法状态减去，于是我们不妨设 (h) 表示需要减去的贡献，(g) 表示二分图的数量，不难得到：
当然，后者需要保证图不连通，所以 (T e S)，这样就得到了一个 (mathcal O(3^n)) 的算法了。
事实上，注意到 (2^{T o Toplus S}) 中，设 (cnt_{S}) 表示点集 (S) 中的边数，那么不难注意到 (cnt_{T o Toplus S}=cnt_{S}-cnt_{T}-cnt_{Toplus S})
然后就可以 FWT 卷一卷了，复杂度 (mathcal O(n^22^n))
不过我非常懒，就写了 (mathcal O(ncdot 2^n+3^n)) 的写法（预处理 cnt 使用高维前缀和算）
(Code:)
#include<bits/stdc++.h>
using namespace std ;
#define Next( i, x ) for( register int i = head[x]; i; i = e[i].next )
#define rep( i, s, t ) for( register int i = (s); i <= (t); ++ i )
#define Rep( i, s, t ) for( register int i = (s); i < (t); ++ i )
#define drep( i, s, t ) for( register int i = (t); i >= (s); -- i )
#define re register
#define int long long
int gi() {
char cc = getchar() ; int cn = 0, flus = 1 ;
while( cc < '0' || cc > '9' ) { if( cc == '-' ) flus = - flus ; cc = getchar() ; }
while( cc >= '0' && cc <= '9' ) cn = cn * 10 + cc - '0', cc = getchar() ;
return cn * flus ;
}
const int P = 998244353 ;
const int Iv = 499122177 ;
const int N = (1 << 17) ;
const int M = 500 + 5 ;
int n, m, f[N], h[N], g[N], fac[M], inv[M] ;
int Get(int x) {
return (x >= 0) ? fac[x] : inv[-x] ;
}
signed main()
{
n = gi(), m = gi() ; int x, y ;
rep( i, 1, m ) x = gi() - 1, y = gi() - 1, f[(1 << x) | (1 << y)] = 1 ;
int lim = (1 << n) - 1 ; fac[0] = inv[0] = 1 ;
Rep( k, 0, n ) rep( i, 1, lim ) if(i & (1 << k)) f[i] += f[i ^ (1 << k)] ;
rep( i, 1, m ) fac[i] = fac[i - 1] * 2 % P, inv[i] = inv[i - 1] * Iv % P ;
rep( S, 1, lim ) {
int p = 0 ;
for(re int j = 0; j < n; ++ j) if((1 << j) & S) { p = (1 << j) ; break ; }
for(re int j = S; ; j = (j - 1) & S ) {
h[S] = (h[S] + inv[f[j] + f[S ^ j]]) % P ;
if( j == 0 ) break ;
}
h[S] = h[S] * fac[f[S]] % P ;
for(re int j = S; j; j = (j - 1) & S ) {
if( !(j & p) ) continue ;
g[S] = (g[S] + fac[f[S] - f[j] - f[S ^ j]]) % P ;
g[S] = (g[S] - g[j] * h[j ^ S] % P + P) % P ;
}
}
cout << g[lim] << endl ;
return 0 ;
}