A 签到

B 二分+抽屉原理

C 简单构造

D dp/不定方程(重点在于约束模型的转化)

A 签到

考虑尽量让两个选手向中间靠拢,如果无法靠拢,就把一个选手在边界调整一轮奇偶性即可,模拟这个过程输出答案.

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> VI;
typedef pair<int,int> pii;
namespace IO{
template<typename T>inline void read(T &x){
x=0;ll f=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f=-f;ch=getchar();}
while(isdigit(ch)){x=x*10+ch-48;ch=getchar();}
x=x*f;
}
}
ll N,A,B;
using namespace IO;
int main()
{
read(N),read(A),read(B);
if(A<B) swap(A,B);
ll ans1,ans2,ans3;
ans1=ans2=ans3=2000000000000000000ll;
if((A-B)%2==0) ans1=(A-B)/2;
else{
ans2=min(((A+B)-1)/2,max(A-1,B-1));
ans3=min(((A-B)-1)/2+N-A+1,max(N-A,N-B));
}

cout<<min(min(ans1,ans2),ans3);
}

B 二分+抽屉原理

首先贪心性显然:如果一个低分值的题目可能被选上,那么比他分值高的题目也一定能被选上.

考虑一个二分,二分排序后第$x$个选手能否被选上.验证这个二分的时候,再考虑贪心性:只有前$p-1$个和第$x$个能被选上.

因此,就可以这样判断:

  • $x\leq p$ ,$x$一定能被选上;

  • $point[x]+m<point[p]$时,即使全部评委给$x$投票 也不够,因此$x$一定无法被选上;

  • 最后我们需要考虑评委数量的问题:有$m$个评委,每个评委能投入$v$张票,因此贪心地想,$1 - (p-1)$和$i(i>x)$的题目即使全部投票 也不会对$x$的正确性产生影响,真正对$x$产生影响的是$i[p\leq i<x]$的题目,如果它们被溢出的票给选上了,就可能对$x$的正确性造成影响.定量地看:每个$i[p\leq i <x]$最多不影响$x$的票数是$point[x]+m-point[i]$.考虑抽屉原理 ,如果一共的票数$mv>$总票数(全部投给对$x$无影响的以及将无所谓的票数投给那些有影响的),那么一定有票数”溢出”了,这些票一定被分在了$i[p\leq i <x]$那先题目了,这样$x$就一定无法选上了.

时间复杂度$O(nlogn)$

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> VI;
typedef pair<int,int> pii;
namespace IO{
template<typename T>inline void read(T &x){
x=0;ll f=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f=-f;ch=getchar();}
while(isdigit(ch)){x=x*10+ch-48;ch=getchar();}
x=x*f;
}
}
using namespace IO;
ll a[100000+10];
ll n,m,v,p;
bool cmp(ll a,ll b)
{
return (a>b);
}
bool judge(ll x)
{
if(x<=p) return true;
if(a[x]+m<a[p]) return false;
if(p-1+n-x>=v) return true;
ll sum=(p)*m+(n-x)*m;
for(int i=p;i<=x-1;i++)
sum+=a[x]+m-a[i];
if(sum<m*v) return false;
else return true;
}
int main()
{
read(n),read(m),read(v),read(p);
for(int i=1;i<=n;i++)
{
read(a[i]);
}
sort(a+1,a+n+1,cmp);
ll l=0,r=n;
while(l<r)
{
ll mid=(l+r+1)/2;
if(judge(mid)) l=mid;
else r=mid-1;
}
cout<<l;
}

C 简单构造

这个构造题比较简单,显然我们只需要构造出$n=4-7$且价值为3的情况,然后在对角线摆放即可.

($n=2$无解),小情况可以手造也可以暴力,当然这题手造也很好造.

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
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
/*
4
aaca
bbca
acbb
acaa
5
b.cca
bc..b
ac..b
abbaa
6
aa.bba
b.cc.a
bc.aa.
.ca..b
a.a..b
abb.aa
7
aa..bba
b.cc..a
bc.aa..
.ca.cc.
..ac..b
a..c..b
abb..aa
*/
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> VI;
typedef pair<int,int> pii;
namespace IO{
template<typename T>inline void read(T &x){
x=0;ll f=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f=-f;ch=getchar();}
while(isdigit(ch)){x=x*10+ch-48;ch=getchar();}
x=x*f;
}
}
using namespace IO;
int n;
int ans[2000][2000];

int main()
{
read(n);
if(n==2) {cout<<"-1";return 0;}
if(n==3){

cout<<"a.."<<endl;
cout<<"a.."<<endl;
cout<<".aa"<<endl;
return 0;
};
int m,mod;
m=n/4-1;
mod=n%4+4;
int x1=0,x2=0,x3=0,x4=0;
for(int j=1;j<=n-mod;j++){
if(j%4==1){
for(int i=1;i<=x1;i++)
cout<<"....";
cout<<"aaca";
for(int i=4*x1+4+1;i<=n;i++)
cout<<".";
cout<<endl;
x1++;
}

if(j%4==2){
for(int i=1;i<=x2;i++)
cout<<"....";
cout<<"bbca";
for(int i=4*x2+4+1;i<=n;i++)
cout<<".";
cout<<endl;
x2++;
}
if(j%4==3){
for(int i=1;i<=x3;i++)
cout<<"....";
cout<<"acbb";
for(int i=4*x3+4+1;i<=n;i++)
cout<<".";
cout<<endl;
x3++;
}
if(j%4==0){
for(int i=1;i<=x4;i++)
cout<<"....";
cout<<"acaa";
for(int i=4*x4+4+1;i<=n;i++)
cout<<".";
cout<<endl;
x4++;
}
}
if(mod==4)
{
for(int i=1;i<=n-4;i++)
cout<<".";
cout<<"aaca"<<endl;
for(int i=1;i<=n-4;i++)
cout<<".";
cout<<"bbca"<<endl;
for(int i=1;i<=n-4;i++)
cout<<".";
cout<<"acbb"<<endl;
for(int i=1;i<=n-4;i++)
cout<<".";
cout<<"acaa"<<endl;
}
if(mod==5)
{
/*
b.cca
bc..b
ac..b
abbaa
*/
for(int i=1;i<=n-5;i++)
cout<<".";
cout<<"aabba"<<endl;
for(int i=1;i<=n-5;i++)
cout<<".";
cout<<"bcc.a"<<endl;
for(int i=1;i<=n-5;i++)
cout<<".";
cout<<"b..cb"<<endl;
for(int i=1;i<=n-5;i++)
cout<<".";
cout<<"a..cb"<<endl;
for(int i=1;i<=n-5;i++)
cout<<".";
cout<<"abbaa"<<endl;
}
if(mod==6)
{
/*
aa.bba
b.cc.a
bc.aa.
.ca..b
a.a..b
abb.aa
*/
for(int i=1;i<=n-6;i++)
cout<<".";
cout<<"aa.bba"<<endl;
for(int i=1;i<=n-6;i++)
cout<<".";
cout<<"b.cc.a"<<endl;
for(int i=1;i<=n-6;i++)
cout<<".";
cout<<"bc.aa."<<endl;
for(int i=1;i<=n-6;i++)
cout<<".";
cout<<".ca..b"<<endl;
for(int i=1;i<=n-6;i++)
cout<<".";
cout<<"a.a..b"<<endl;
for(int i=1;i<=n-6;i++)
cout<<".";
cout<<"abb.aa"<<endl;
}

if(mod==7)
{
/*
aa..bba
b.cc..a
bc.aa..
.ca.cc.
..ac..b
a..c..b
abb..aa
*/
for(int i=1;i<=n-7;i++)
cout<<".";
cout<<"aa..bba"<<endl;
for(int i=1;i<=n-7;i++)
cout<<".";
cout<<"b.cc..a"<<endl;
for(int i=1;i<=n-7;i++)
cout<<".";
cout<<"bc.aa.."<<endl;
for(int i=1;i<=n-7;i++)
cout<<".";
cout<<".ca.cc."<<endl;
for(int i=1;i<=n-7;i++)
cout<<".";
cout<<"..ac..b"<<endl;
for(int i=1;i<=n-7;i++)
cout<<".";
cout<<"a..c..b"<<endl;
for(int i=1;i<=n-7;i++)
cout<<".";
cout<<"abb..aa";
}
}

D dp/不定方程

这个题难点在于模型的转化,转化以后代码仅仅30行不到.

首先考虑贪心性,我们要满足的情况是
$$
\forall k,~~\sum_{i=1}^{k+1}A_i>\sum_{i=n-k+1}^{n}A_i
$$
观察这个式子我们发现由于$A_i$的单调性,所以只用考虑前一半和后一半的总和的约束即可,即$k=n/2$.

由于$A_i$具有单调性,我们不太好直接统计$A_i$序列的方案数,因此我们可以设$A_i=1+\sum_{j=1}^ix_j$:

这样我们就把$A_i$的计数转化成了$x_i$的不带单调条件的计数.

在$k=n/2$处改写为$x_i$的约束条件:

  • $\sum_{i=1}^n x_i < n$
  • $1+x_1> \sum_{i=2}^{n}(i\leq (n>>1)+1?i-2:n-i+1)x_i$

然后我们发现我们我们可以把计数改为带约束的$x_1$的计数和不带约束的$x_2 -x_n $的计数.$x_1$的情况只和$\sum_{i=2}^{n}(i\leq (n>>1)?i-1:n-i+2)x_i$有关,因此我们可以设计一个不定方程模型:$dp[i][j]$表示考虑到第$i$个未知数和为$j$的情况总数,这个$dp$可以很简单地类似完全背包地转移出来,统计总的情况数,题目就被解决了.

(可能可以生成函数推式子?存疑)

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn =5005;
ll dp[maxn][maxn],n,mod;
ll c[maxn];
int main()
{
cin>>n>>mod;
for(int i=2;i<=n;i++)
{
c[i]=(i<=(n>>1)+1?i-1:n-i+2);
}
// dp[i][j]=dp[i][j-c[i]]+dp[i-1][j]
for(int i=0;i<=n;i++)
dp[i][0]=1;
for(int i=2;i<=n;i++)
for(int j=0;j<=n;j++)
{
if(j>=c[i])dp[i][j]=(dp[i][j-c[i]]+dp[i-1][j]+mod)%mod;
else dp[i][j]=dp[i-1][j];
}
ll ans=0;
for(int i=0;i<n;i++)
ans=(ans+(n-i)*dp[n][i]%mod)%mod;
cout<<ans;
}