今天是2020.10.10，记录一下这三天的刷题。
前天晚上有场cf：
Codeforces Round #747 (Div. 2)
A. Consecutive Sum Riddle（思维）
题意：
给出数n，求两个数x和y，使得x+ x+1 + x+2 + … + y-1 + y = n。
n≤1e18，-1e18≤x<y≤1e18。
思路：
x和y都可以取负数，所以可以让0左右两边的数都抵消掉，只剩下n就可。
所以x=-n+1，y=n。
B. Special Numbers（思维，二进制）
题意：
给出一个数x，问由 x 0 , x 1 , x 2 , x 3 . . . x^0, x^1, x^2, x^3... x0,x1,x2,x3...组成的 第 k 大 数 第k大数 第k大数 mod 1 e 9 + 7 1e9+7 1e9+7 后为多少？
思路：
x
a
+
x
a
=
x
a
+
1
x^a + x^a = x^{a+1}
xa+xa=xa+1—— 存在进位关系。
将k二进制分解，将k的二进制看作答案的二进制，然后用x恢复出来答案的十进制。
Code：
const int N = 200010, mod = 1e9+7;
ll T, n, m, a[N];
int main(){
Ios;
cin>>T;
while(T--)
{
cin>>n>>m;
int t=m,cnt=0;
while(t!=0)
{
a[++cnt]=t%2;
t/=2;
}
ll ans=0,tt=1;
for(int i=1;i<=cnt;i++){
ll t=(ll)a[i]*tt%mod;
tt=(ll)tt*n%mod;
ans=(ll)(ans+t)%mod;
}
cout<<ans<<"\n";
}
return 0;
}
C. Make Them Equal（思维）
题意：
给出长度为n的字符串，要转化为元素都为字符a的串。最小执行多少次下述操作？
取一个数x，每次可以将 不是x的倍数的位置上的数 变为字符a。
输出最少操作数和对应的x。
思路：
- 如果最后一个元素不需要变化的话，直接取x为n，那么除了n这个位置，其他所有位置都可以变为目标元素。用一次操作。
- 最后一个元素需要变化：
1、如果n/2+1这个位置到n位置中，有不需要变化的元素的话，就选这个位置，那么所有位置都会变为目标元素，用一次操作。
2、如果没有的话，就要用两次操作了，取x为 n 和 n-1。
Code：
const int N = 300010, mod = 1e9+7;
int T, n, m;
char a[N];
bool f[N];
int main(){
Ios;
cin>>T;
while(T--)
{
char c;
cin>>n>>c;
int cnt=0;
for(int i=1;i<=n;i++){
f[i]=0;
cin>>a[i];
if(a[i]!=c) cnt++,f[i]=1;
}
if(cnt==0){
cout<<0<<"\n";continue;
}
if(a[n]==c){
cout<<1<<"\n";
cout<<n<<"\n";
}
else{
int flag=0;
for(int i=n;i>=1;i--){
if(!f[i]){
flag=i;break;
}
}
if(flag>n/2){
cout<<1<<"\n";
cout<<flag<<"\n";
}
else{
cout<<2<<"\n";
cout<<n-1<<" "<<n<<"\n";
}
}
}
return 0;
}
E1. Rubik’s Cube Coloring (easy version)（组合）
题意：
需要给一个深度为n的满二叉树的节点染色，需要满足：
一条边连接的两个节点的颜色在魔方的配色中是相邻的 。
问，一共有多少种不同的方法将这棵满二叉树染色？答案 mod 1e9+7。
思路：
好像和著名的四色定理差不多。
第一个点，也就是根节点有六种染色方式。其余的所有节点都有4中染色方式。
一共
2
n
?
1
2^{n}-1
2n?1个节点，所以最终的染色方式一共有：
6
?
4
2
n
?
2
6*4^{2^{n}-2}
6?42n?2 种。
4
2
n
?
2
4^{2^{n}-2}
42n?2 可以用快速幂，边乘边取模。但是需要注意的是，求
2
n
?
2
2^n-2
2n?2不能取模！
因为这个结果是作为4的幂次，而取模运算会导致答案错误。
Code：
const int N = 200010, mod = 1e9+7;
int T, n, m, a[N];
ll qmi(ll x,ll y)
{
ll ans=1;
while(y)
{
if(y&1) ans=(ans*x)%mod;
x=(ll)x*x%mod;
y>>=1;
}
return ans;
}
int main(){
Ios;
cin>>n;
ll t=(ll)pow(2,n)-2;
cout<<(ll)6*qmi(4,t)%mod;
return 0;
}
D. The Number of Imposters (代更。。）
…
昨天上午有场人工智能编程大赛的初赛，A题有个技巧没能想起来。。
题意：
给出n个数，给出m次询问，每次询问有k个数。n≤50。
如果k个数都满足 是n个数中的四个数的平均数，输出Yes；否则输出No。
思路：
当时脑子一片空白，只能打了个暴力。。
一共m*k个数需要判断，暴力的话是 m ? k ? n ? n ? n m*k*n*n*n m?k?n?n?n。。铁定超。。
但是n很小，所以完全可以预处理出n个数从中取4个能够组成哪些数，map标记下来，然后O(1)查询。。
。。
昨晚Atcoder有场ABC：
AtCoder Beginner Contest 222
C - Swiss-System Tournament（模拟）
题意：
2 * n个人进行比赛，一共m局，每局两两pk，位置为2i的人和位置2i-1的人pk。
每局结束后，位置会变化。变化规则：
1.根据从开局到现在的胜利局数从大到小排序。
2.两人tie时，根据编号排序，编号小的在前面。
思路：
就是结构体存储下位置和胜利局数，每局结束后排序就行。
一开始题读错了，然后这道题折腾了一个多小时。。
有个需要注意的点：
如果将一个数组排序，根据cmp排序的话，cmp函数 int x,int y，这个x和y其实是a[i]和a[j]，并不是下标。
Code：
const int N = 2010, mod = 1e9+7;
int T, n, m;
char a[N][N];
int b[N],c[N];
struct NN{
int id,w;
}cnt[N];
int better(char x,char y){
if(x=='G'){
if(y=='G') return 0;
else if(y=='C') return 1;
return 2;
}
if(x=='C'){
if(y=='C') return 0;
else if(y=='G') return 2;
else return 1;
}
if(x=='P'){
if(y=='P') return 0;
else if(y=='C') return 2;
return 1;
}
}
bool cmp(NN a,NN b){
if(a.w!=b.w) return a.w>b.w;
return a.id<b.id;
}
int main(){
cin>>n>>m;
n*=2;
for(int i=1;i<=n;i++){
cnt[i].id=i;
for(int j=1;j<=m;j++){
cin>>a[i][j];
}
}
for(int i=1;i<=m;i++)
{
for(int j=1;j<=n;j++)
{
if(j%2==0) continue;
int t=better(a[cnt[j].id][i],a[cnt[j+1].id][i]);
if(t==1) cnt[j].w++; //注意这里是j，不是cnt[j].id！
else if(t==2) cnt[j+1].w++;
}
sort(cnt+1,cnt+n+1,cmp);
}
for(int i=1;i<=n;i++) cout<<cnt[i].id<<endl;
return 0;
}
D - Between Two Arrays（dp，前缀和）
题意：
给出两个不下降数列a和b，其中每个位置满足
a
[
i
]
≤
b
[
i
]
a[i]≤b[i]
a[i]≤b[i]。
构造一个不下降数列c，其中每个位置满足：
a
[
i
]
≤
c
[
i
]
≤
b
[
i
]
a[i]≤c[i]≤b[i]
a[i]≤c[i]≤b[i]。问一共有多少种构造方式？
思路：
把每个位置上能放下的值列出来，发现是这样的：
1 1 1
2 2 2
3 3
4
那么以当前位置 i 上的数 j 结尾的数列c的个数 就可以由上一位置的所有不超过 j 的所有状态转移过来。
但是如果要遍历上一位置上不超过j的所有数的话就超时了。
所以可以每次在更新完成之后，维护当前位置的从1到 j 的前缀和，这样下一个位置就直接用该位置更新了。
Code：
const int N = 3010, mod = 998244353;
int T, n, m;
PII a[N];
int f[N][N];
signed main(){
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i].fi;
for(int i=1;i<=n;i++) cin>>a[i].se;
int ans=0;
for(int i=1;i<=n;i++)
{
for(int j=a[i].first;j<=a[i].second;j++)
{
f[i][j]=f[i-1][j]; //直接由上一位置的前缀更新
if(i==1) f[i][j]=1;
if(i==n) ans=(ans+f[i][j])%mod;
}
for(int j=1;j<=3000;j++) f[i][j]=(f[i][j]+f[i][j-1])%mod; //维护状态前缀
}
cout<<ans;
return 0;
}
今晚有场cf：
Educational Codeforces Round 115 (Rated for Div. 2)
B. Groups（暴力，思维）
题意：
一共n个同学（n为偶数），给出一个n*5的矩阵 ，表示每名同学在周一到周五是否有空。
现要挑选一周里的两天x,y。问，是否有n/2个人在周x有空并且另外n/2个人在周y有空？
思路：
遍历枚举选择的两天x和y：判断这两天合不合适。
如果满足：
1、在这两天中，n个人都有空闲时间；
2、在周x有空闲时间的人不少于n/2，在周y有空闲时间的人不少于n/2：
那就说明：有n/2在周x有空闲时间，并且另外n/2个人在周y有时间。
Code：
const int N = 200010, mod = 1e9+7;
int T, n, m, a[N][6];
bool f[N];
bool pd(int x,int y)
{
int cnt1=0,cnt2=0;
for(int i=1;i<=n;i++){
f[i]=0;
if(a[i][x]) cnt1++,f[i]=1;
if(a[i][y]) cnt2++,f[i]=1;
}
for(int i=1;i<=n;i++){
if(!f[i]) return 0;
}
if(cnt1>=n/2&&cnt2>=n/2) return 1;
return 0;
}
int main(){
Ios;
cin>>T;
while(T--)
{
cin>>n;
for(int i=1;i<=n;i++)
for(int j=1;j<=5;j++)
cin>>a[i][j];
bool flag=0;
for(int i=1;i<=5;i++){
for(int j=i+1;j<=5;j++){
if(pd(i,j)){
flag=1;
}
}
}
if(flag) cout<<"YES\n";
else cout<<"NO\n";
}
return 0;
}
C. Delete Two Elements （map）
题意：
给出n个数，所有数之和为sum。现在要从中选择两个位置上的数删掉。
问满足删掉之后的
s
u
m
′
(
n
?
2
)
=
s
u
m
/
n
sum' (n-2) = sum/n
sum′(n?2)=sum/n 的位置选择有多少种方式？
思路：
设删掉位置上的两个数之和为 x。 那么，
s
u
m
′
=
s
u
m
?
x
sum' = sum - x
sum′=sum?x .
化简一下得：
x
=
s
u
m
?
s
u
m
?
(
n
?
2
)
/
n
x = sum - sum*(n-2) / n
x=sum?sum?(n?2)/n。
所以遍历所有位置，判断有多少个 x ? a [ i ] x-a[i] x?a[i] 在数列中就行了。
如果当前x-a[i]=a[i]的话，记得减掉一次。
前面的数加上后面了，后面又加前面数一遍，所以方案数多了一倍，最终的答案要除2。
注意x可能为小数！
Code：
const int N = 200010, mod = 1e9+7;
int T, n, m;
double a[N];
signed main(){
Ios;
cin>>T;
while(T--)
{
cin>>n;
double sum=0;
mp.clear();
for(int i=1;i<=n;i++) cin>>a[i],sum+=a[i],mp[a[i]]++;
double x=sum-sum*(n-2)*1.0/n;
int ans=0;
for(int i=1;i<=n;i++){
if(x-a[i]==a[i]) ans--;
ans+=mp[x-a[i]];
}
cout<<ans/2<<"\n";
}
return 0;
}
D. Training Session （代更。。）
…
明天加油！