Codeforces Global Round 14 补题
每次全球场都好自闭，但是又不容易掉分。
思路
一组数据
因为每个元素都不同，如果我们避开了这一个元素，可能这个元素后面几个元素的和仍然等于这个元素。
如果$sum=x$，则一定无解。否则的话，我们在输出的时候记录一下是否输出下一个元素前缀和就达到了$x$，如果是的话，那么我们将这个元素向后推，因为所有元素都不同，一定会有解。
思路
看一个大正方形能由多少个小正方形组成，并将这些小正方形切开（2或4）.
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
|
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int ll
typedef pair<int,int>pii;
const int maxn=2e5+10,inf=0x3f3f3f3f,mod=1000000007;
signed main(signed argc, char const *argv[])
{
std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
int t,n;
cin>>t;
while(t--)
{
cin>>n;
bool ok=0;
int x,g;
if(n%2==0)
{
x=n/2;
g=sqrt(x);
if(g*g==x)
ok=1;
if(n%4==0)
{
x=n/4;
g=sqrt(x);
if(g*g==x)
ok=1;
}
}
cout<<(ok?"YES":"NO")<<endl;
}
return 0;
}
|
思路
贪心地将每一个砖块加入到当前最小的塔上，为什么这种策略是最优的呢。
因为每一个砖块高度都不会超过$x$，如果当前所有的塔都是合法的，令$a$为当前最大元素，$b$为当前最小元素，$h_i$为此时砖块高度，那么$b+h_i - a\le x$，仍为合法状态。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
| #include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int ll
typedef pair<int,int>pii;
const int maxn=2e5+10,inf=0x3f3f3f3f,mod=1000000007;
struct node
{
int id,val;
bool operator <(const node &y)const
{
return val>y.val;
}
};
int h[maxn],ans[maxn],tower[maxn];
signed main(signed argc, char const *argv[])
{
std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
int t,n,m,x;
cin>>t;
while(t--)
{
cin>>n>>m>>x;
priority_queue<node>q;
for(int i=1;i<=n;i++)
cin>>h[i];
for(int i=1;i<=m;i++)
{
tower[i]=0;
q.push(node{i,0});
}
for(int i=1;i<=n;i++)
{
node now=q.top();
q.pop();
ans[i]=now.id;
tower[now.id]+=h[i];
q.push(node{now.id,tower[now.id]});
}
if(*max_element(tower+1,tower+m+1)<=*min_element(tower+1,tower+m+1)+x)
{
cout<<"YES"<<endl;
for(int i=1;i<=n;i++)
cout<<ans[i]<<' ';
}
else{
cout<<"NO";
}
cout<<endl;
}
return 0;
}
|
思路
左集合和右集合中相同颜色的袜子可以直接0代价消除，之后我们需要将大的集合中的袜子转变为另一个集合中的袜子。
同一个集合内的袜子可以通过1代价消除，但是如果我们消耗了小的集合中的两只相同颜色袜子，会额外产生两个空缺，需要通过大的集合花费4代价来补足，消耗这2+4只袜子便一共花费了5代价；而直接从大的集合转移一只袜子到小集合则花费4代价。
所以不断消耗大集合内的同颜色袜子使其大小接近小集合的策略才是最优的。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
|
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int ll
typedef pair<int,int>pii;
int c[maxn];
signed main(signed argc, char const *argv[])
{
std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
int t,n,l,r;
cin>>t;
while(t--)
{
cin>>n>>l>>r;
map<int,int>left,right;
for(int i=1;i<=n;i++)
{
cin>>c[i];
if(i<=l)
left[c[i]]++;
else{
if(left[c[i]]>0)
left[c[i]]--;
else
right[c[i]]++;
}
}
int cl=0,cr=0;
for(int i=1;i<=n;i++)
cl+=left[i],cr+=right[i];
if(cl<cr)
{
swap(cl,cr);
swap(left,right);
}
int dis=(cl-cr)/2,ans=0;
for(int i=1;i<=n;i++)
{
while(left[i]>=2&&dis)
{
ans++;
dis--;
left[i]-=2;
}
if(dis==0)
break;
}
cout<<ans+cr+dis*2<<endl;
}
return 0;
}
|
不会dp，不会组合数学，坐等掉分。
题意
有$n$台电脑排成一排，你要把所有电脑都打开，当一台关着的电脑两边的电脑都打开之后也会打开，你不能重复开启电脑。
请计算开启所有电脑的方案数。
思路
Codeforces Global Round 14 E. Phoenix and Computers
先考虑一段长度为$k$的电脑，我们不通过自动开启的方案数有多少种。很明显我们如果开了一台电脑，那我们只能从已经点亮的这一段向左右扩展，否则最终合并时一定会被自动点亮。
如果我们点开了1号电脑，我们只能一直向右点亮电脑，一共有$C_{k-1}^{0}$种方案（类似从$(0,0)$走到$(n,m)$有几种走法）。
如果我们点开了2号电脑，左面有1台电脑，右面有$k-2$台，一共有$k-1$次操作，此时方案数$C_{k-1}^{1}$。
如果我们点开了3号电脑，左面有2台电脑，右面有$k-3$台，一共有$k-1$次操作，此时方案数$C_{k-1}^{2}$。
所以综上，全手动开启一段长度为$k$的电脑有$C_{k-1}^{0}+C_{k-1}^{1}+C_{k-1}^{2}+\dots +C_{k-1}^{k-1}=2^{k-1}$种方案。
所以，任何一段电脑的打开方案都是由一段手动打开和一台自动开启交替进行，为了$dp$方便，默认以自动开启结尾，可以通过取$dp[n+1]$的方案来获得答案。
令$dp[i][j]$表示前$i-1$台电脑手动打开了$j$台，第$i$台为自动打开的方案数。
那么$dp[i][j]\rightarrow dp[i+1+k][j+k]$的意义为：
第$i-1$台为一段手动打开的电脑的末尾，第$i$台自动开启，后面接着一段长度为$k$的需要手动开启的电脑，第$i+k+1$台电脑自动开启。
我们需要将新来的$k$台需要手动开启的电脑所做的贡献$2^{k-1}$与之前$j$台手动打开的电脑的方案数$dp[i][j]$合并在一起，相当于我一共有$j+k$个指令要做，其中有$j$个$a$指令，$k$个$b$指令，一共有$C_{j+k}^k$个不同的指令序列。
$$
dp[i+1+k][j+k]+=dp[i][j]\times 2^{k-1}\times C_{j+k}^{k}
$$
最后计算$\sum\limits_{i=0}^{n}dp[n+1][i]$即为答案。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
|
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int ll
const int maxn=455,inf=0x3f3f3f3f;
ll fac[maxn],inv[maxn],a[maxn],mod;
ll quick(ll a,ll b){
ll ans=1;
while(b){
if(b&1)ans=ans*a%mod;
a=a*a%mod;
b/=2;
}
return ans%mod;
}
ll ccc(ll n,ll m){
if(n<m)
return 0;
else if(n==m)
return 1;
return fac[n]*inv[m]%mod*inv[n-m]%mod;
}
void initccc(ll n)
{
fac[0] = 1;
for (int i = 1; i <= n ;i++){
fac[i] = fac[i - 1] * i % mod;
}
inv[n]=quick(fac[n],mod-2);
for(int i=n-1;i>=1;i--)
inv[i]=inv[i+1]*(i+1ll)%mod;
}
ll dp[maxn][maxn];
signed main(signed argc, char const *argv[])
{
ll n,m,ans=0;
cin>>n>>mod;
initccc(n+50);
dp[0][0]=1;
for(int i=0;i<n;i++)
{
for(int j=0;j<=i;j++)
{
for(int k=1;k+i<=n;k++)
{
dp[i+1+k][j+k]+=dp[i][j]*quick(2,k-1)%mod*ccc(j+k,k)%mod;
dp[i+1+k][j+k]%=mod;
}
}
}
for(int i=0;i<=n;i++)
ans=(ans+dp[n+1][i])%mod;
cout<<ans<<endl;
return 0;
}
|