Codeforces Round 981 (Div. 3)（A-F）
Codeforces Round 981 (Div. 3)（A-F）
题目传送门
这场难度严重与题号不符合。
个人感觉是
C
>
F
>
E
>
D
>
A
>
B
C>F>E>D>A>B
C>F>E>D>A>B
A. Sakurako and Kosuke
思路
题很简单，但是我看错了， K o s u k e Kosuke Kosuke和 S a k u r a k o Sakurako Sakurako各有一个点，然后就想着推式子，推了一半开始打暴力，后来发现是只有一个点，哦，那没事了，那就是我们可以发现两个人每次都会将这个点往自己的方向拉回一格，所以考虑奇偶性即可，奇数就是 K o s u k e Kosuke Kosuke赢，偶数则是 S a k u r a k o Sakurako Sakurako赢。
代码
#pragma GCC optimize(3)
#pragma GCC target("avx")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fstrict-overflow")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
#pragma GCC optimize(2)
#include <bits/stdc++.h>
#define inf 0x3f3f3f3f
#define ll long long
#define lowbit(x) x&(-x)
#define x first
#define y second
#define IOS ios::sync_with_stdio(false);cin.tie(nullptr),cout.tie(nullptr);
#define two(x) __builtin_popcount(x)
using namespace std;
typedef pair<ll,ll> PII;
typedef pair<ll,string> PIS;
const int mod=1e9+7;
const int N=1e6+10;
//ll qmi(ll a,ll b){ll res=1ll;while(b){if(b&1) res=res*a;b>>=1;a=(a)*(a);}return res;}
ll qmi(ll a,ll b,ll mod){ll res=1ll;while(b){if(b&1) res=(res%mod)*a%mod;b>>=1;a=(a%mod)*(a%mod)%mod;}return res%mod;}
//const int N=2001020;
ll gcd(ll x,ll y){return y?gcd(y,x%y):x;} //最大公约数
ll fact[N],infact[N];
void c(ll mod){fact[0]=infact[0]=1;for(ll i=1;i<=N-5;i++){fact[i]=(i%mod*fact[i-1]%mod)%mod;infact[i]=(infact[i-1]%mod)*(qmi(i,mod-2,mod)%mod)%mod;}}
ll C(ll a,ll b,ll mod){return ((fact[a]%mod*infact[b]%mod)%mod*(infact[a-b]%mod)%mod)%mod;}//组合数
void solve(){
int n;
cin>>n;
if(n%2==1) cout<<"Kosuke\n";
else cout<<"Sakurako\n";
}
int main(){
IOS
//int _;
//c(mod);
int _=1;
cin>>_;
while(_--) solve();
return 0;
}
B. Sakurako and Water
思路
我们发现这题就是每次可以找每条主对角线上负数绝对值的最大值，因为我们每次做多操作一条主对角线上的所有负数，所以找绝对值的最大值即可，然后求和。
代码
#pragma GCC optimize(3)
#pragma GCC target("avx")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fstrict-overflow")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
#pragma GCC optimize(2)
#include <bits/stdc++.h>
#define inf 0x3f3f3f3f
#define ll long long
#define lowbit(x) x&(-x)
#define x first
#define y second
#define IOS ios::sync_with_stdio(false);cin.tie(nullptr),cout.tie(nullptr);
#define two(x) __builtin_popcount(x)
using namespace std;
typedef pair<ll,ll> PII;
typedef pair<ll,string> PIS;
const int mod=1e9+7;
//ll qmi(ll a,ll b){ll res=1ll;while(b){if(b&1) res=res*a;b>>=1;a=(a)*(a);}return res;}
ll qmi(ll a,ll b,ll mod){ll res=1ll;while(b){if(b&1) res=(res%mod)*a%mod;b>>=1;a=(a%mod)*(a%mod)%mod;}return res%mod;}
//const int N=2001020;
ll gcd(ll x,ll y){return y?gcd(y,x%y):x;} //最大公约数
//ll fact[N],infact[N];
//void c(ll mod){fact[0]=infact[0]=1;for(ll i=1;i<=N-5;i++){fact[i]=(i%mod*fact[i-1]%mod)%mod;infact[i]=(infact[i-1]%mod)*(qmi(i,mod-2,mod)%mod)%mod;}}
//ll C(ll a,ll b,ll mod){return ((fact[a]%mod*infact[b]%mod)%mod*(infact[a-b]%mod)%mod)%mod;}//组合数
//ll ans=0;
const int N=510;
ll g[N][N];
ll ans=0;
void solve(){
int n;
ans=0;
cin>>n;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
cin>>g[i][j];
}
}
for(int i=n;i>=1;i--){
ll maxn=0;
for(int j=i;j<=n;j++){
if(g[j][j-i+1]<0){
maxn=max(maxn,abs(g[j][j-i+1]));
}
}
ans+=maxn;
}
for(int i=n;i>=1;i--){
ll maxn=0;
for(int j=i;j<=n;j++){
if(g[j-i+1][j]<0){
maxn=max(maxn,abs(g[j-i+1][j]));
}
}
if(i!=1) ans+=maxn;
}
cout<<ans<<"\n";
}
int main(){
IOS
//int _;
//c(mod);
int _=1;
cin>>_;
while(_--) solve();
return 0;
}
C. Sakurako’s Field Trip
思路
这题可以暴力做，很显然，我们只需要考虑前 n 2 \frac{n}{2} 2n项即可，那我们只需要考虑每一项 ( i ) (i) (i)前后与他的镜像 ( n − i + 1 ) (n-i+1) (n−i+1)前后的四项是否在交换前后的相等对数的变化，如果变多了，那就不换，变少了就换，不变说明没影响，换与不换都行。但是这样做真的很复杂，而且很容易出边界问题。
我们仔细考虑一下，首先，对于长度为 2 2 2和 3 3 3的数组，我们无论怎么换，其结果都是一样的，因为两者都是第一个与最后一个换，随后，我们去考虑长度为 4 4 4和 5 5 5的情况，我们发现 1 1 1和 4 4 4换与不换是等价于 2 2 2和 3 3 3是否可以需要换的，那么我们去考虑一下是不是 1 1 1和 n n n都不需要交换。
我们推广到长度为 n n n的数组 ( n ≥ 6 ) (n\geq6) (n≥6)的情况:我们发现可以从第 2 2 2项开始，枚举到第 n 2 \frac{n}{2} 2n项，对于第 k ∈ [ 2 , n 2 ] k\in[2, \frac{n}{2}] k∈[2,2n]项而言，镜像索引 n − k + 1 n-k+1 n−k+1，我们都只考虑第 k − 1 k-1 k−1和第 n − k + 2 n-k+2 n−k+2项，如果能满足交换后相等的数量变少就交换，不变少就不交换，这样递推下去，我们最终发现最后一定能好推到剩 2 2 2项或者 3 3 3项，即第 n 2 \frac{n}{2} 2n和 第 n 2 + 1 第\frac{n}{2}+1 第2n+1或第 n 2 \frac{n}{2} 2n和 第 n 2 + 1 第\frac{n}{2}+1 第2n+1和第 n 2 + 2 \frac{n}{2}+2 2n+2这两种情况，而这两种情况在前面已经正面他们是否交换与本身并没有关系，只与他们前者有关系，那么这就形成了闭环，证明了我们可以不交换第 1 1 1和第 n n n项。
这样我们就得出了最后的做法 : : : 从第 2 2 2项开始枚举到第 n 2 \frac{n}{2} 2n项，每次考虑交换前后是否有相等数增减来决定是否交换，最后再循环一遍所有相等的数个数即得到答案。
代码
#pragma GCC optimize(3)
#pragma GCC target("avx")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fstrict-overflow")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
#pragma GCC optimize(2)
#include <bits/stdc++.h>
#define inf 0x3f3f3f3f
#define ll long long
#define lowbit(x) x&(-x)
#define x first
#define y second
#define IOS ios::sync_with_stdio(false);cin.tie(nullptr),cout.tie(nullptr);
#define two(x) __builtin_popcount(x)
using namespace std;
typedef pair<ll,ll> PII;
typedef pair<ll,string> PIS;
const int mod=1e9+7;
//ll qmi(ll a,ll b){ll res=1ll;while(b){if(b&1) res=res*a;b>>=1;a=(a)*(a);}return res;}
ll qmi(ll a,ll b,ll mod){ll res=1ll;while(b){if(b&1) res=(res%mod)*a%mod;b>>=1;a=(a%mod)*(a%mod)%mod;}return res%mod;}
//const int N=2001020;
ll gcd(ll x,ll y){return y?gcd(y,x%y):x;} //最大公约数
//ll fact[N],infact[N];
//void c(ll mod){fact[0]=infact[0]=1;for(ll i=1;i<=N-5;i++){fact[i]=(i%mod*fact[i-1]%mod)%mod;infact[i]=(infact[i-1]%mod)*(qmi(i,mod-2,mod)%mod)%mod;}}
//ll C(ll a,ll b,ll mod){return ((fact[a]%mod*infact[b]%mod)%mod*(infact[a-b]%mod)%mod)%mod;}//组合数
//ll ans=0;
const int N=1e5+510;
ll s[N],a[N];
ll ans=0;
int res=0;
bool check(int i,int j,int x,int y){
int xd=0,xd1=0;
if(a[i]==a[j]) xd++;
if(a[x]==a[y]) xd++;
if(a[x]==a[j]) xd1++;
if(a[y]==a[i]) xd1++;
res+=min(xd,xd1);
return xd>xd1;
}
void solve(){
int n;
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
}
res=0;
for(int i=2;i<=n;i++){
if(a[i]==a[i-1]) res++;
}
if(n<=3){
cout<<res<<"\n";
return;
}
res=0;
for(int i=2;i<=n/2;i++){
if(check(i,i-1,n-i+1,n-i+2)){
swap(a[i],a[n-i+1]);
}
}
ll p=0;
for(int i=2;i<=n;i++){
p+=(a[i]==a[i-1]);
}
cout<<p<<"\n";
}
int main(){
IOS
//int _;
//c(mod);
int _=1;
cin>>_;
while(_--) solve();
return 0;
}
D. Kousuke’s Assignment
思路
D D D相比于 C C C来说思维含量就低多了，也常规了很多，很显然的贪心 + + +前缀和，我们经过简单的思考即可发现显然是越早遇到区间和为 0 0 0的区段，越早切割更优，我们求前缀和 s [ i ] s[i] s[i]，然后对于每个 s [ i ] s[i] s[i]，如果之前出现过且出现的位置再前一段已经切割的位置之后，那么我们就可以在当前段切割，顺便更新一下最大切割位置。
代码
#pragma GCC optimize(3)
#pragma GCC target("avx")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fstrict-overflow")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
#pragma GCC optimize(2)
#include <bits/stdc++.h>
#define inf 0x3f3f3f3f
#define ll long long
#define lowbit(x) x&(-x)
#define x first
#define y second
#define IOS ios::sync_with_stdio(false);cin.tie(nullptr),cout.tie(nullptr);
#define two(x) __builtin_popcount(x)
using namespace std;
typedef pair<ll,ll> PII;
typedef pair<ll,string> PIS;
const int mod=1e9+7;
//ll qmi(ll a,ll b){ll res=1ll;while(b){if(b&1) res=res*a;b>>=1;a=(a)*(a);}return res;}
ll qmi(ll a,ll b,ll mod){ll res=1ll;while(b){if(b&1) res=(res%mod)*a%mod;b>>=1;a=(a%mod)*(a%mod)%mod;}return res%mod;}
//const int N=2001020;
ll gcd(ll x,ll y){return y?gcd(y,x%y):x;} //最大公约数
//ll fact[N],infact[N];
//void c(ll mod){fact[0]=infact[0]=1;for(ll i=1;i<=N-5;i++){fact[i]=(i%mod*fact[i-1]%mod)%mod;infact[i]=(infact[i-1]%mod)*(qmi(i,mod-2,mod)%mod)%mod;}}
//ll C(ll a,ll b,ll mod){return ((fact[a]%mod*infact[b]%mod)%mod*(infact[a-b]%mod)%mod)%mod;}//组合数
//ll ans=0;
const int N=1e5+510;
ll s[N];
ll ans=0;
void solve(){
int n;
cin>>n;
vector<ll> a(n+1);
for(int i=1;i<=n;i++){
cin>>a[i];
s[i]=0;
}
ll ans=0;
map<ll,ll> mp;
for(int i=1;i<=n;i++){
s[i]=s[i-1]+a[i];
}
int maxn=-1;
mp[0]=0;
for(int i=1;i<=n;i++){
if(mp.count(s[i])){
if(mp[s[i]]>maxn){
ans++;
maxn=i-1;
}
mp[s[i]]=i;
}else mp[s[i]]=i;
}
cout<<ans<<"\n";
}
int main(){
IOS
//int _;
//c(mod);
int _=1;
cin>>_;
while(_--) solve();
return 0;
}
E. Sakurako, Kosuke, and the Permutation
思路
E E E是一个经典的置换环问题（ P S : PS: PS:其实我之前都不知道置换环，我是找规律过的这题），这里给个置换环知识学习的链接 : : :
我们很显然发现，如果将这个数组按照题目要求排序后，每个数要么是自环 ( a [ i ] = = i ) (a[i]==i) (a[i]==i)，要么有且只能与一个数形成环，即 ( a [ a [ i ] ] = = i ) (a[a[i]]==i) (a[a[i]]==i)，为什么呢，因为我们可以考虑这个意思就是 a [ i ] a[i] a[i]向 i i i连了一条边，而 a [ i ] ≠ i a[i] \neq i a[i]=i，因次如果 i i i不向 a [ i ] a[i] a[i]连一条边则推出了 a [ i ] ≠ a [ i ] a[i]\neq a[i] a[i]=a[i]，因此将这个数列转化为图一定是若干个自环和若干个两数环所组成的图。所以对于一个 a [ i ] = i a[i]=i a[i]=i或者 a [ a [ i ] ] = i a[a[i]]=i a[a[i]]=i的数，我们可以不做任何处理，而遇到了 a [ i ] ≠ i a[i]\neq i a[i]=i的数，我们就假设 a [ a [ i ] ] = i a[a[i]]=i a[a[i]]=i，即 a [ i ] = p a[i]=p a[i]=p，那么我们也要将 a [ p ] a[p] a[p]改为 i i i，交换一下即可，这样必定可以一次修改两个数，肯定是优于将 a [ i ] a[i] a[i]改成 i i i的这种做法的。
代码
#pragma GCC optimize(3)
#pragma GCC target("avx")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fstrict-overflow")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
#pragma GCC optimize(2)
#include <bits/stdc++.h>
#define inf 0x3f3f3f3f
#define ll long long
#define lowbit(x) x&(-x)
#define x first
#define y second
#define IOS ios::sync_with_stdio(false);cin.tie(nullptr),cout.tie(nullptr);
#define two(x) __builtin_popcount(x)
using namespace std;
typedef pair<ll,ll> PII;
typedef pair<ll,string> PIS;
const int mod=1e9+7;
//ll qmi(ll a,ll b){ll res=1ll;while(b){if(b&1) res=res*a;b>>=1;a=(a)*(a);}return res;}
ll qmi(ll a,ll b,ll mod){ll res=1ll;while(b){if(b&1) res=(res%mod)*a%mod;b>>=1;a=(a%mod)*(a%mod)%mod;}return res%mod;}
//const int N=2001020;
ll gcd(ll x,ll y){return y?gcd(y,x%y):x;} //最大公约数
//ll fact[N],infact[N];
//void c(ll mod){fact[0]=infact[0]=1;for(ll i=1;i<=N-5;i++){fact[i]=(i%mod*fact[i-1]%mod)%mod;infact[i]=(infact[i-1]%mod)*(qmi(i,mod-2,mod)%mod)%mod;}}
//ll C(ll a,ll b,ll mod){return ((fact[a]%mod*infact[b]%mod)%mod*(infact[a-b]%mod)%mod)%mod;}//组合数
//ll ans=0;
const int N=1e5+510;
ll s[N];
ll ans=0;
void solve(){
int n;
cin>>n;
int ans=0;
vector<int> a(n+1);
map<int,int> mp;
for(int i=1;i<=n;i++){
cin>>a[i];
mp[a[i]]=i;
}
for(int i=1;i<=n;i++){
if(a[i]==i || a[a[i]]==i){
continue;
}else{
int s=mp[i];
int t=a[i];
swap(a[s],a[t]);
mp[a[s]]=s;
mp[a[t]]=t;
ans++;
}
}
cout<<ans<<"\n";
}
int main(){
IOS
//int _;
//c(mod);
int _=1;
cin>>_;
while(_--) solve();
return 0;
}
F. Kosuke’s Sloth
思路
这题其实采用了很常用的一种做法，当第一眼看题没有思路的时候，那就打表，（暴力出奇迹，打表拿省一） 对于不同的
n
,
k
n,k
n,k，我们可以设置较小的打表范围，发现对于每个
k
k
k，找到第
1
1
1个
f
b
i
[
i
]
m
o
d
k
=
0
fbi[i] \bmod k=0
fbi[i]modk=0，之后想找第几项
×
n
\times n
×n即可。我们经过简单的打表也发现了，最多找
k
k
k次必然可以找到第
1
1
1个使
f
b
i
[
i
]
m
o
d
k
=
0
fbi[i] \bmod k=0
fbi[i]modk=0的值，由于题目说了
∑
k
<
1
e
6
\sum_{}k \lt 1e6
∑k<1e6，故直接枚举即可，时间复杂度
O
(
k
)
O(k)
O(k)。
代码
#pragma GCC optimize(3)
#pragma GCC target("avx")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fstrict-overflow")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
#pragma GCC optimize(2)
#include <bits/stdc++.h>
#define inf 0x3f3f3f3f
#define ll long long
#define lowbit(x) x&(-x)
#define x first
#define y second
#define IOS ios::sync_with_stdio(false);cin.tie(nullptr),cout.tie(nullptr);
#define two(x) __builtin_popcount(x)
using namespace std;
typedef pair<ll,ll> PII;
typedef pair<ll,string> PIS;
const int mod=1e9+7;
//ll qmi(ll a,ll b){ll res=1ll;while(b){if(b&1) res=res*a;b>>=1;a=(a)*(a);}return res;}
ll qmi(ll a,ll b,ll mod){ll res=1ll;while(b){if(b&1) res=(res%mod)*a%mod;b>>=1;a=(a%mod)*(a%mod)%mod;}return res%mod;}
//const int N=2001020;
ll gcd(ll x,ll y){return y?gcd(y,x%y):x;} //最大公约数
//ll fact[N],infact[N];
//void c(ll mod){fact[0]=infact[0]=1;for(ll i=1;i<=N-5;i++){fact[i]=(i%mod*fact[i-1]%mod)%mod;infact[i]=(infact[i-1]%mod)*(qmi(i,mod-2,mod)%mod)%mod;}}
//ll C(ll a,ll b,ll mod){return ((fact[a]%mod*infact[b]%mod)%mod*(infact[a-b]%mod)%mod)%mod;}//组合数
//ll ans=0;
const int N=1e5+510;
ll n,k;
ll f[N];
void solve(){
cin>>n>>k;
f[1]=f[2]=1;
ll s=0;
for(int i=1;i<=N-100;i++){
if(i>=3) f[i]=(f[i-1]+f[i-2])%k;
if(f[i]%k==0){
s=i;
break;
}
}
cout<<s%mod*(n%mod)%mod<<"\n";
}
int main(){
IOS
int _;
cin>>_;
while(_--) solve();
return 0;
}
继续训吧！
开放原子开发者工作坊旨在鼓励更多人参与开源活动，与志同道合的开发者们相互交流开发经验、分享开发心得、获取前沿技术趋势。工作坊有多种形式的开发者活动，如meetup、训练营等，主打技术交流，干货满满，真诚地邀请各位开发者共同参与！
更多推荐
27
0- 0
已为社区贡献1条内容
所有评论(0)