本场链接:Codeforces Global Round 14
闲话
看不懂E,F不知道什么时候能补出来.
A. Phoenix and Gold
题目大意:给定\(n,x\),以及一个数组\(w\).要求重排\(w\),使得不存在某个\(j\)满足\(\sum\limits_{i = 1}^j w_i = x\),即不存在一个前缀和累加起来得到\(x\).保证元素互不相同.
首先特判掉一种情况:整个数组的和就是\(x\),显然无解.
如果\(w\)本来就没有一个前缀和\(=x\)那么直接输出就完事了,但是如果存在呢?因为每两个元素互不相同,如果\(i\)位置的前缀和与\(x\)相等,那么将\(w_i\)与任何一个\(j > i\)的\(w_j\)交换之后必然能使这个前缀和不等于\(x\).为了避免之后还会出现\(x\),不妨将整个数组排序,那么这样前缀和就是单调的,直接swap破坏了性质的位置和下一个位置的元素即可.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define forn(i,x,n) for(int i = x;i <= n;++i)
#define forr(i,x,n) for(int i = n;i >= x;--i)
#define Angel_Dust ios::sync_with_stdio(0);cin.tie(0)
const int N = 105;
int w[N];
int main()
{
int T;scanf("%d",&T);
while(T--)
{
int n,x;scanf("%d%d",&n,&x);
int sum = 0;
forn(i,1,n) scanf("%d",&w[i]),sum += w[i];
if(sum == x)
{
puts("NO");
continue;
}
sort(w + 1,w + n + 1);
int cur = 0;
forn(i,1,n - 1)
{
cur += w[i];
if(cur == x)
{
swap(w[i],w[i + 1]);
break;
}
}
puts("YES");
forn(i,1,n) printf("%d ",w[i]);
puts("");
}
return 0;
}
B. Phoenix and Puzzle
给定\(n\)个等腰直角三角形,问能不能把他们拼成一个正方形.不能相互覆盖,必须全部使用.
如果把边长定义为\(1\),不难找到最基本的两种构造是长度为\(1\)的正方形和长度为\(\sqrt(2)\)的正方形,其余的情况不过是这两种堆叠而成的.两者需要的三角形个数分别是\(2\),\(4\).对于一个有\(i*i\)个基本元素(前面两种)的正方形,需要的个数就是\(i^2*2\)或者\(i^2*4\).所以只需要检查\(n/2\)或者\(n/4\)是否是平方数即可.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define forn(i,x,n) for(int i = x;i <= n;++i)
#define forr(i,x,n) for(int i = n;i >= x;--i)
#define Angel_Dust ios::sync_with_stdio(0);cin.tie(0)
int main()
{
int T;scanf("%d",&T);
while(T--)
{
int n;scanf("%d",&n);
if(n == 1)
{
puts("NO");
continue;
}
bool ok = 0;
int n2 = n / 2,sqn2 = sqrt(n2);
if(n % 2 == 0 && 1ll * sqn2 * sqn2 == n2) ok = 1;
int n4 = n / 4,sqn4 = sqrt(n4);
if(n % 4 == 0 && 1ll * sqn4 * sqn4 == n4) ok = 1;
if(ok) puts("YES");
else puts("NO");
}
return 0;
}
C. Phoenix and Towers
题目大意:有\(n\)个砖,每个高度为\(h_i\),要求拿这些砖头堆出\(m\)座塔,每个塔的高度就是使用的砖块高度之和.不能有一个塔的高度为\(0\),每个砖块必须使用.构造一个任意两座塔的高度之差都不严格超过\(x\)的方案.
不难想到一个更强的目标:使最大的高度之差最小,这看起来像是一个二分答案,但是实现check摆脱不了\(O(n^2)\)的枚举,考虑直接贪心:对于每个元素,将他放在当前高度最低的塔中,这样构造的高度是最平均的.因为如果交换两个元素,等价于选择的时候某个元素就没有选入当前高度最小的塔,这样势必会让差距变大.
代码里的做法要更拐弯一些:因为要保证所有塔高度平均,所以在第一轮分配的时候首先把所有砖块尽量往高度之和的平均值去凑.第二轮的时候就没得选了直接放.没什么具体差别.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
#define forn(i,x,n) for(int i = x;i <= n;++i)
#define forr(i,x,n) for(int i = n;i >= x;--i)
#define Angel_Dust ios::sync_with_stdio(0);cin.tie(0)
#define x first
#define y second
const int N = 1e5+7;
int h[N],ans[N];
bool st[N];
int main()
{
int T;scanf("%d",&T);
while(T--)
{
int n,m,x;scanf("%d%d%d",&n,&m,&x);
int allsum = 0;
forn(i,1,n) scanf("%d",&h[i]),allsum += h[i],st[i] = 0;
int target = allsum / m;
priority_queue<pii,vector<pii>,greater<pii>> q;
forn(i,1,m) q.push({0,i});
forn(i,1,n)
{
auto _ = q.top();q.pop();
if(_.x + h[i] <= target)
{
_.x += h[i];
st[i] = 1;
ans[i] = _.y;
}
q.push(_);
}
forn(i,1,n)
{
if(st[i]) continue;
auto _ = q.top();q.pop();
_.x += h[i];
st[i] = 1;
ans[i] = _.y;
q.push(_);
}
vector<int> ans_c;
while(!q.empty()) ans_c.push_back(q.top().x),q.pop();
sort(ans_c.begin(),ans_c.end());
if(ans_c.back() - ans_c[0] > x) puts("NO");
else
{
puts("YES");
forn(i,1,n) printf("%d ",ans[i]);
puts("");
}
}
return 0;
}
D. Phoenix and Socks
一共有\(n\)条袜子,保证\(n\)是偶数.每个袜子有自己的方向和颜色,一对袜子是匹配的当且仅当颜色相同且一左一右.你可以花\(1\)块钱使袜子的颜色变成指定颜色,或是让他的方向变换一次.求最少花费多少能使\(n\)条袜子各自匹配.
- 一开始就可以匹配上的直接全部删掉
- 如果当前左方向的数量\(l\)与右方向\(r\)不相同,意味着多的一方需要先调转一些方向与自己集合里的匹配,不妨讨论\(l<r\)的情形,这时如果右方向的集合中有某些相同颜色的,则可以花费\(1\)的代价调转他们的方向使得匹配上.
- 如果\(l\)还是不相同于\(r\),则意味着某些袜子必须要调转方向还要换色再与右袜子中的匹配.那么首先有\(l\)个可以只换一次颜色就能与之匹配上,还有\(r-l\)个必须要换了颜色还要换方向,总的代价就是\((r-l)*2+l\).
- 如果是匹配的,那么只需要换颜色就可以了,代价是\(l\).
另外一种情况对称处理即可.
注意不要一边遍历一边删除.可能会引发迭代器失效.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
#define forn(i,x,n) for(int i = x;i <= n;++i)
#define forr(i,x,n) for(int i = n;i >= x;--i)
#define Angel_Dust ios::sync_with_stdio(0);cin.tie(0)
#define x first
#define y second
const int N = 2e5+7;
int c[N];
int main()
{
int T;scanf("%d",&T);
while(T--)
{
int n,l,r;scanf("%d%d%d",&n,&l,&r);
forn(i,1,n) scanf("%d",&c[i]);
map<int,int> L,R;
forn(i,1,l) ++L[c[i]];
forn(i,l + 1,n) ++R[c[i]];
for(auto& _ : L)
{
int v = _.x;
if(!R.count(v)) continue;
int cost = min(_.y,R[v]);
L[v] -= cost;R[v] -= cost;
}
int szL = 0,szR = 0,res = 0;
for(auto& _ : L) szL += _.y;
for(auto& _ : R) szR += _.y;
if(szL != szR)
{
if(szL < szR)
{
for(auto& _ : R)
{
if(_.y == 1) continue;
while(_.y >= 2 && szL < szR)
{
szR -= 2;
_.y -= 2;
++res;
}
}
}
else
{
for(auto& _ : L)
{
if(_.y == 1) continue;
while(_.y >= 2 && szR < szL)
{
szL -= 2;
_.y -= 2;
++res;
}
}
}
}
if(szL < szR) res += szR;
else if(szL > szR) res += szL;
else res += szL;
printf("%d\n",res);
}
return 0;
}
E. Phoenix and Computers
题目大意:有\(n\)个机子,你可以手动开某些机子.这些机子比较牛逼,当位于\(i-1\)和\(i+1\)的机子同时开启时,位于\(i\)的机子会自动启动.求:手动开启机子位置序列的方案数,要求所有机子最后都开启.
如果从左到右去看整个操作序列,那么就可以这么看:先手动开了\(1,2,3...i_1 - 1\)的机子,之后\(i_1\)的机子自动开启.再往下就是\(i_1+1...i_2 - 1\)的机子手动去开,\(i_2\)的机子自动打开.按每个自动开启的机子分段.
考虑DP:
- 状态:\(f[i][j]\)表示启动了\(i\)台机子,其中前\(i-1\)个里有\(j\)个是自己手动开的,并且第\(i\)个是自动打开的方案数.
- 入口:\(f[0][0] = 1\).
- 转移:把每个自动开启的位置作为分段条件,那么每次实际上就是插入一段长度为\(k\)的段,并且这一段全部都是手动打开的,对于这一段本身的方案数稍后讨论.其次这个长度为\(k\)的段可以随意插入当前已经有\(j\)个手动开的位置中间,那么方案数系数有\(C_{j+k}^k\).而对于长度为\(k\)的段来说因为要全部手动打开,所以开启方式是比较固定的:如果起点是\(i\)的话,那么接下来会有\(k-1\)个位置,这\(k-1\)个位置需要穿插放入前\(i-1\)个数,剩下的位置只能是连续的放置\(i+1,i+2,i+3...\),所以方案数就是\(C_{k - 1}^i\),所有的方案数就是\(C_{k-1}^{0}+C_{k-1}^{1}+...C_{k-1}^{k-1} = 2^{k - 1}\).转移就是\(f[i + k + 1][j + k] += f[i][j] * 2 ^{k - 1} * C_{j + k}^{k}\).
- 出口:\(\sum\limits_{i=1}^nf[n+1][i]\).
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define forn(i,x,n) for(int i = x;i <= n;++i)
#define forr(i,x,n) for(int i = n;i >= x;--i)
#define Angel_Dust ios::sync_with_stdio(0);cin.tie(0)
const int N = 405;
int C[N][N],f[N][N],pw2[N];
int n,MOD;
void init()
{
pw2[0] = 1;
forn(i,1,N - 1) pw2[i] = 2ll * pw2[i - 1] % MOD;
forn(i,0,N - 1) forn(j,0,i)
{
if(!j) C[i][j] = 1;
else C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % MOD;
}
}
int main()
{
scanf("%d%d",&n,&MOD);
init();
f[0][0] = 1;
forn(i,0,n - 1) forn(j,0,i) forn(k,1,n - i)
f[i + k + 1][j + k] = (f[i + k + 1][j + k] + 1ll * f[i][j] * C[j + k][k] % MOD * pw2[k - 1] % MOD) % MOD;
int res = 0;
forn(i,0,n) res = (res + f[n + 1][i]) % MOD;
printf("%d\n",res);
return 0;
}
F. Phoenix and Earthquake
题目大意:给定一个\(n\)点,\(m\)边的无向图.所有的边都被摧毁了,现在要求重建\(n-1\)条边,重建一条边的代价是\(x\).每个点都有原材料\(a_i\)组,当两个点之间重建的时候,两者拥有的材料会合并在一起重建.所有连通在一起的点原材料也会合并.问是否能构造一个重建方案.
不难把原来的题意转换成:每次合并两个点,满足这两个点的点权之和\(\geq x\).并且连边合并最后得到一棵树.
首先可以列出无解情况:当所有原材料加起来都不够构造一棵树,即\(\sum a_i < (n-1)*x\)时,无解.
其他情况,贪心:考虑一个迭代过程,每次取出权值最大的点\(u\),因为想要点权和\(\geq x\),之后连向此点的一个不连通的邻居\(v\).再将\(v\)的权值合并到\(u\),同时要将\(v\)的边集合并到\(u\)上,这一步可以启发式合并,保证时空复杂度.
迭代的第一步的正确性:假如这个点权值\(a_u \geq x\),那么与任何一个点合并都不会违反规则,正确性显然.如果这个点\(a_u < x\),由于它是最大值,意味着其他点不会比之更大,一开始的时候又保证了\(\sum a_i \geq (n-1)*x\),所以如果和足够\((n-1)*x\)的话应该存在某个点\(a_v \geq x\),矛盾了.所以取出的最大值一定是一个\(\geq x\)的值,不存在较小值合并的情况.
迭代的次数比较显然是\(n-1\),因为每次会建出一条边,树一共有\(n-1\)条边.
迭代的合并部分实现:首先连通性可以用并查集维护,迭代开始时,使用的点应该是一个没有被合并的点,这一步检查可以看取出的点是否是并查集的根.其次很容易想到这个题还需要合并边集,如果直接大力合并的话肯定是不行的,考虑启发式合并:将较小的邻接表直接insert到较大的邻接表后面,这样的空间复杂度会降低到\(O(log(n))\).就避免了MLE问题.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,int> pli;
typedef pair<int,int> pii;
#define forn(i,x,n) for(int i = x;i <= n;++i)
#define forr(i,x,n) for(int i = n;i >= x;--i)
#define Angel_Dust ios::sync_with_stdio(0);cin.tie(0)
#define x first
#define y second
const int N = 3e5+7;
vector<pii> E[N];
int fa[N];
ll a[N];
int find(int x)
{
if(x == fa[x]) return x;
return fa[x] = find(fa[x]);
}
int main()
{
int n,m,x;scanf("%d%d%d",&n,&m,&x);
ll sum = 0;
forn(i,1,n) scanf("%lld",&a[i]),sum += a[i];
if(sum < 1ll * x * (n - 1)) return puts("NO"),0;
forn(i,1,m)
{
int u,v;scanf("%d%d",&u,&v);
E[u].push_back({v,i});
E[v].push_back({u,i});
}
priority_queue<pli> q;
forn(i,1,n) q.push({a[i],i}),fa[i] = i;
puts("YES");
forn(___,2,n)
{
int u = q.top().y;q.pop();
while(find(u) != u) u = q.top().y,q.pop();
while(find(u) == find(E[u].back().x)) E[u].pop_back();
printf("%d\n",E[u].back().y);
int v = find(E[u].back().x);
fa[v] = u;
a[u] += a[v] - x;
q.push({a[u],u});
if(E[u].size() < E[v].size()) swap(E[u],E[v]);
E[u].insert(E[u].end(),E[v].begin(),E[v].end());
E[v].clear();
}
return 0;
}