2021牛客暑期多校训练营1
文章目录
A: Alice and Bob
解释
暴力打表，由必败状态确定必胜状态。
结论：对于第有一堆为i大小的石头，存在最多一堆为j的石头为必败状态。
证明：设当前有两堆（i，p），（i，q），q > p，且为后手必胜状态。那么将（i，q）拿走（0，q-p）个后变成（i，p），那么（i，q）应该为先手必胜，故与假设矛盾。
那么枚举（i，j），当这个为必败状态时扩展这个点。复杂度O( n 2 l o g n n^2logn n2logn) .
代码
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#include<bits/stdc++.h>
using namespace std;
const int N = 5e3 + 10;
const int mod = 1e9 + 7;
const double eps = 1e-9;
typedef long long ll;
//#define int long long
bool f[N][N];
void get(){
for(int i=0;i<N;i++)
for(int j=0;j<N;j++)
if(f[i][j] == 0){
for(int k=1;i+k<N;k++)
for(int s=0;s*k+j<N;s++)
f[i+k][j+s*k] = 1;
for(int k=1;j+k<N;k++)
for(int s=0;s*k+i<N;s++)
f[i+s*k][j+k] = 1;
}
}
signed main(){
IOS
get();
int tt; cin>>tt;
while(tt --){
int n,m; cin>>n>>m;
if(f[n][m]) cout<<"Alice"<<endl;
else cout<<"Bob"<<endl;
}
return 0;
}
B: Ball Dropping
解释
Δ E G H ～ Δ D F C \Delta{EGH}\sim \Delta{DFC} ΔEGH～ΔDFC 故 E G D F = E H D C \frac{EG}{DF} = \frac{EH}{DC} DFEG?=DCEH? Δ D J H ～ Δ D F C \Delta{DJH} \sim \Delta{DFC} ΔDJH～ΔDFC 故 D J D F = J H F C \frac{DJ}{DF} = \frac{JH}{FC} DFDJ?=FCJH? 即可以得到 D J DJ DJ 即 m m m 的高度。
那么 E H = r × h 2 + ( a ? b 2 ) 2 h EH = \frac{r\times\sqrt{h^2+(\frac{a-b}{2})^2}}{h} EH=hr×h2+(2a?b?)2?? D J = E H ? b 2 a ? b 2 × h DJ = \frac{EH-\frac{b}{2}}{\frac{a-b}{2}}\times h DJ=2a?b?EH?2b??×h
当 b > 2 ? r b > 2*r b>2?r 时，上述不成立，即为Drop.
代码
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#include<bits/stdc++.h>
using namespace std;
const double eps = 1e-7;
#define C(x) ((x)*(x))
signed main(){
IOS
long double r,a,b,h; cin>>r>>a>>b>>h;
long double EH = r*sqrt(C(h)+C((a-b)/2)) / h;
long double DJ = (EH - b/2) / ((a-b)/2) * h;
if(b > 2 * r) cout<<"Drop"<<endl;
else {
cout<<"Stuck"<<endl;
cout<<fixed<<setprecision(7)<<DJ<<endl;
}
return 0;
}
D: Determine the Photo Position
解释
统计每一行中连续0的个数，每一行分别处理
代码
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
string s[N];
signed main(){
int n,k; cin>>n>>k;
for(int i=1;i<=n;i++) cin>>s[i];
cin>>s[n+1];
int cnt = 0,ans = 0;
for(int i=1;i<=n;i++){
for(int j=0;j<n;j++){
if(s[i][j] == '0'){
cnt ++;
}else{
if(cnt >= k){
ans += cnt - k + 1;
}
cnt = 0;
}
}
if(cnt >= k) ans += cnt - k + 1;
cnt = 0;
}
cout<<ans<<endl;
return 0;
}
F: Find 3-friendly Integers
解释
大于等于100的一定包含3的倍数
代码
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
const int mod = 1e9 + 7;
const double eps = 1e-9;
#define int long long
int slove(int x){
int cnt = 0;
for(int i=1;i<=x;i++){
if(i % 3 == 0) cnt ++;
else{
if(i >= 10){
if(i%10%3 == 0 || i/10 % 3 == 0) cnt ++;
}
}
}
return cnt;
}
signed main(){
int tt; cin>>tt;
while(tt --){
int l,r; cin>>l>>r;
int ll = min(l,99ll);
int rr = min(r,99ll);
cout<<slove(rr)+(r - rr) - slove(ll-1) - (l - ll)<<endl;
}
return 0;
}
G: Game of Swapping Numbers
解释
- 将 a i , b i a_i,b_i ai?,bi? 看成一个区间，考虑交换所产生的值。
- 对于n > 2， b i ? a i < = 0 b_i-a_i <= 0 bi??ai?<=0 或者 b i ? a i = > 0 b_i-a_i => 0 bi??ai?=>0 都会出现两次 以上，则对于k次交换，可以取任意次拿来做无意义的交换。n=2特判。
- 下面是区间交换会产生的结果。
存下 m i n ( a i , b i ) ， m a x ( a i , b i ) min(a_i,b_i)，max(a_i,b_i) min(ai?,bi?)，max(ai?,bi?)的值，排序，取尽可能大的值。那就要优先取 m i n ( a i , b i ) ? m a x ( a j , b j ) min(a_i,b_i)-max(a_j,b_j) min(ai?,bi?)?max(aj?,bj?) 最大的。
代码
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e6 + 10;
int a[N],b[N],mi[N],ma[N];
signed main(){
IOS
int n,k; cin>>n>>k;
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1;i<=n;i++) cin>>b[i];
for(int i=1;i<=n;i++) ma[i] = max(a[i],b[i]),mi[i] = min(a[i],b[i]);
int ans = 0;
if(n == 2){
if(k % 2) swap(a[1],a[2]);
ans = abs(a[1]-b[1]) + abs(a[2]-b[2]);
}else{
sort(mi+1,mi+n+1);sort(ma+1,ma+n+1);
reverse(mi+1,mi+n+1);
for(int i=1;i<=n;i++) ans += abs(a[i]-b[i]);
for(int i=1;i<=min(n,k);i++) if(mi[i] > ma[i]) ans += 2 * (mi[i] - ma[i]);
}
cout<<ans<<endl;
return 0;
}
H: Hash Function
解释
由题目得出 ( a % m o d ≠ b % m o d ) = ( a ? b ) % m o d ≠ 0 (a\%mod \neq b\%mod) = (a-b)\%mod \neq 0 (a%mod?=b%mod)=(a?b)%mod?=0 即所有数的差值不能被mod整除, 对于求所有数的差值。暴力是 n 2 n^2 n2 ，可以用FFT/NNT加速多项式相乘求解。
为什么能用多项式？
-
假设x,y,z都是多项式，且为 k 1 × x 1 1 + k 2 × x 2 2 + . . . + k n × x n n k_1\times x_1^1 + k_2 \times x_2^2 + ... + k_n \times x_n^n k1?×x11?+k2?×x22?+...+kn?×xnn? 这种形式，下标与指数一一对应。
-
假设 k i k_i ki?表示 i 这个值是否出现在差值序列中， k i > = 1 k_i >= 1 ki?>=1 说明存在。
-
c = a ? b = > p ( c ) = p ( a ? b ) = > p ( c ) = p ( a ) × p ( ? b ) c = a - b => p(c) = p(a-b) => p(c) = p(a) \times p(-b) c=a?b=>p(c)=p(a?b)=>p(c)=p(a)×p(?b) , p ( c ) 等 价 于 x c p(c) 等价于 x^c p(c)等价于xc
-
多项式相乘后，x每一项都会和y所有项进行组合。相当于a中的所有数和其它的值求了差值，只是多项式表示是否存在。
-
构造两个多项式，对于每一个数，它对于差值的贡献为 a 和 -a，构造x和y两个多项式系数，初始化x的第a项系数为1,y的第-a项系数为1。
-
项数不存在负数，加一个偏移量P。
-
FFT/NNT复杂度为 O ( n l o g n ) O(nlogn) O(nlogn)
-
最后得到的序列系数，第i位对应的值为，i - P 。从 大于等于 P开始枚举。
代码
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#include<bits/stdc++.h>
using namespace std;
const int N = 3e6 + 10;
typedef complex<double> CP;
const double Pi = acos(-1);
const int P = 500001;
CP a[N],b[N];
bool vis[N];
void FFT(CP *x,int lim,int inv){
int bit = 1,m;
CP stand,now,temp;
while((1<<bit) < lim) ++bit;
for(int i=0;i<lim;++i){
m = 0;
for(int j=0;j<bit;++j) if(i & (1<<j)) m |= (1<<(bit-j-1));
if(i<m) swap(x[m],x[i]);
}
for(int len=2;len<=lim;len<<=1){
m = len >> 1;
stand = CP(cos(2*Pi/len),inv*sin(2*Pi/len));
for(CP *p=x; p!=x+lim;p+=len){
now = CP(1,0);
for(int i=0;i<m;++i,now*=stand){
temp = now * p[i+m];
p[i+m] = p[i] - temp;
p[i] = p[i] + temp;
}
}
}
if(inv == -1) for(int i=0;i<lim;++i) x[i].real(x[i].real()/lim);
}
bool check(int x){
for(int i=x;i<=P;i+=x) if(vis[i] == 1) return 0;
return 1;
}
signed main(){
IOS
int n; cin>>n;
for(int i=1;i<=n;i++){
int x; cin>>x;
a[x].real(1);
b[P-x].real(1);
}
int m = 1 << 20; // 500000 转2进制为1 << 20 位
FFT(a,m,1); FFT(b,m,1);
for(int i=0;i<m;i++) a[i] *= b[i];
FFT(a,m,-1);
for(int i=P;i<m;i++){
int k = (int)(a[i].real() + 0.5);
if(k > 0) vis[i-P] = true;
}
for(int i=n;;i++){
if(check(i)){
cout<<i<<endl;
break;
}
}
return 0;
}
I: Increasing Subsequence*
解释
代码
K: Knowledge Test about Match
解释
贪心策略，枚举每一个差值是否出现，出现则匹配。每次先放右边的数和先放左边的数不影响最后结果，因为题目数据保证随机的。根据数据范围n^2也能过，最多有40组数据等于1000。
sqrt函数性质，（部分小的差值+部分大的差值） 比 （中等大小的差值）优。
代码
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e4 + 10;
int ans[N],cnt[N];
signed main(){
int tt; cin>>tt;
while(tt --){
for(int i=0;i<=1000;i++) cnt[i] = 0,ans[i] = -1;
int n; cin>>n;
for(int i=1;i<=n;i++) {
int x; cin>>x;
cnt[x] ++;
}
for(int d=0;d<=n;d++)
for(int i=0;i<n;i++){
if(ans[i] != -1) continue;
if(i+d < n && cnt[i+d]){
ans[i] = i+d;
cnt[i+d] --;
}else if(i-d >= 0 && cnt[i-d]){
ans[i] = i-d;
cnt[i-d] --;
}
}
for(int i=0;i<n;i++) cout<<ans[i]<<" ";
cout<<endl;
}
return 0;
}