文章目录
- [A. Sakurako and Kosuke](https://mirror.codeforces.com/contest/2033/problem/A)
- 思路:
- Solved:
- [B. Sakurako and Water](https://mirror.codeforces.com/contest/2033/problem/B)
- 思路:
- Solved:
- [C. Sakurako's Field Trip](https://mirror.codeforces.com/contest/2033/problem/C)
- 思路:
- Solved:
- [D. Kousuke’s Assignment](https://codeforces.com/contest/2033/problem/D)
- 思路:
- Solved:
- [E. Sakurako, Kosuke, and the Permutation](https://mirror.codeforces.com/contest/2033/problem/E)
- 思路:
- Solved:
- [F. Kosuke's Sloth](https://mirror.codeforces.com/contest/2033/problem/F)
- 思路:
- Solved:
A. Sakurako and Kosuke
思路:
赛时读完题就去写了一个循环去模拟两者操作并记录次数,游戏结束时奇数次操作为先手win,偶数次操作为后手win,后来发现每次操作只会向目标方向移动一格,所以如果到n格,n为奇数时,为先手者到n格,后手win,反之先手win
Solved:
void solve()
{
int n;cin>>n;
int x=1;
int p=0;
int cnt=0;
for(int i=1;i<=10000;i++){
if(p<-n||p>n){
break;
}
if(i&1){
p+=x;
}else{
p-=x;
}
cnt++;
x+=2;
}
if(cnt&1){
cout<<"Sakurako"<<endl;
}else{
cout<<"Kosuke"<<endl;
}
}
void solve()
{
int n;cin>>n;
if(n&1){
cout<<"Kosuke"<<endl;
}else{
cout<<"Sakurako"<<endl;
}
}
B. Sakurako and Water
思路:
赛时读题发现只需要记录每个主对角线上最小的那个数即可,发现数据较小,直接暴力枚举了每个点及其对角线上的所有点
Solved:
void solve()
{
int n;cin>>n;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
cin>>a[i][j];
}
}
int ans=0;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
int mi=0;
for(int k=0;k<=n;k++){
int x=i+k,y=j+k;
if(x>n||y>n){
break;
}
if(a[x][y]<mi){
mi=a[x][y];//只要最小的
}
if(a[x][y]<0){//负数改为0
a[x][y]=0;
}
}
ans+=labs(mi);
}
}
cout<<ans<<endl;
}
void solve()
{
int n;cin>>n;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
cin>>a[i][j];
}
}
int ans=0;
//每个元素只遍历一遍
for(int i=1;i<=n;i++){//上三角主对角线
int mi=0;
for(int j=0;j<=n;j++){
int x=1+j,y=i+j;
if(x>n||y>n){
break;
}
mi=min(mi,a[x][y]);
}
ans+=labs(mi);
}
for(int i=2;i<=n;i++){//ctrl+v下三角
int mi=0;
for(int j=0;j<=n;j++){
int x=i+j,y=1+j;
if(x>n||y>n){
break;
}
mi=min(mi,a[x][y]);
}
ans+=labs(mi);
}
cout<<ans<<endl;
}
C. Sakurako’s Field Trip
思路:
赛时读题后想到一种暴力做法,分别枚举出本体和镜像对于左右邻居交换与不交换产生的影响,如果交换前影响 大于 交换后,就应该换,但是会出现严重的边界问题
例如:4 3 3 3 1 2 1 4 1
不论从左枚举还是从右枚举,在 3 3 3 这组数中,明显应该交换中间的3,一次就可以解决,但是如果顺序枚举左右,就会导致左边或者右边的3先进行交换
解决办法:
对于只有2或3个数,发现无论怎么交换,都无法改变他们的邻居
对于4或5个数,发现交换1,5和交换2,4他们对应的单边邻居依然是相同的
1 2 3 4 5
交换(2 , 4),1的邻居为4
交换(1 , 5),1的邻居依然为4
那么继续推,对于6或7个数单边邻居依然如此,所以只用考虑一边,递推至另一边,所有的情况就考虑完全了
Solved:
void solve()
{
int n;cin>>n;
a[n+1]=0;
for(int i=1;i<=n;i++){
cin>>a[i];
}
int lmid=n/2,rmid=n/2+1;//1 2 3 4 根据分析,从1,4分别开始定义l,r
if(n%2==1){//1 2 3 4 5 , 根据分析,从1,5开始
lmid=n/2,rmid=n/2+2;
}
for(int i=lmid-1,j=rmid+1;i>=1;){
int lst1=0,rst1=0;//交换前状态
int lst2=0,rst2=0;//交换后状态
if(a[i]==a[i+1]){//只考虑单边邻居
lst1++;
}
if(a[j]==a[j-1]){
rst1++;
}
if(a[i]==a[j-1]){
lst2++;
}
if(a[j]==a[i+1]){
rst2++;
}
if(lst1+rst1>lst2+rst2){//交换状态后更优则交换
swap(a[i],a[j]);
}
i--;
j++;
}
int ans=0;
for(int i=1;i<=n;i++){//记录结果
if(a[i]==a[i+1]){
ans++;
}
}
cout<<ans<<endl;
return ;
}
D. Kousuke’s Assignment
思路:
对于本题来说,可以先考虑一种局部最优解情况
1 0 -1 ,肯定是选择0单独作为一段为最优,如果选择了1 0 -1,将可能会少计算一段,所以完美线段长度越短越好
例如-1 1 0 -1 1 ,此时,应该选-1 1和0 和-1 1为最优
递推到全局会发现,只要出现某一段为0,就应该将该段最小化并记录,顺序遍历即为答案
Solved:
void solve()
{
map<int,int> mp;
int n;cin>>n;
int sum=0,ans=0;
for(int i=1;i<=n;i++){
int x;cin>>x;
sum+=x;
if(sum==0){
//如果有一段sum=0,出现了完美段,记录ans,重置所有判断条件
mp.clear();
ans++;
sum=0;
continue;
}
if(mp[sum]>0){
//如果在一段中sum出现了两次,就有可能在这之间+0或者加上了一对相反数如1,-1,出现了完美段,记录ans,重置所有判断条件
mp.clear();
ans++;
sum=0;
continue;
}
mp[sum]++;//记录此时段总和
}
cout<<ans<<endl;
}
E. Sakurako, Kosuke, and the Permutation
思路:
看题解有大佬给了一个置换环知识点
对于本题来说,理解一下题意会发现每个位置上最优只会存在两种状态
- 自己与自己形成一个环 Pi = i
- 自己与另一个位置形成一个环(2) P[ Pi ] = i P[ i ] = Pi 也就是说i , j形成一个环满足p[ i ] = j , p[ j ] = i
通过以上推断,就可以明显看出,如果满足题意,该位置可以不换,否则,应先满足第二个条件
过程中应先将每个位置的a[i]与i连接一条边,以确保在二条件更换中快速确定位置
Solved:
void solve(){
int n;cin>>n;
map<int,int> mp;
for(int i=1;i<=n;i++){
cin>>a[i];
mp[a[i]]=i;
//例如,1号位置为3,那么应将1号位对应的mp[1]=3,将1号位和3号位连一条边
}
int ans=0;
for(int i=1;i<=n;i++){
if(a[i]==i||a[a[i]]==i){
continue;
}else{
//不满足题意时,优先二条件更换
int s=mp[i];//取出对应a[i]满足条件的点
int t=a[i];//取出a[a[i]]
swap(a[s],a[t]);//将a[a[i]]和a[mp[i]]交换满足二条件
swap(mp[a[s]],mp[a[t]]);//同时交换两数在a[]中对应位置,此时a[i]号位与1号位成二元环,最优
ans++;//记录
}
}
cout<<ans<<endl;
}
F. Kosuke’s Sloth
思路:
斐波那契数列有一个性质,如果第i项是k的倍数,那么第ni项也是k的倍数
该题可以通过打表斐波那契数列找到第一个k的倍数,对应*n就是第n项
但是数据范围可能很大,需要把握好取模条件
Solved:
void solve(){
int n,k;cin>>n>>k;
f[1]=1;
if(f[1]%k==0){
cout<<n%mod<<endl;
return ;
}
f[2]=1;
int ans=0;
for(int i=3;i<=10000000;i++){
f[i]=(f[i-1]+f[i-2])%k;//f[i-1]+f[i-2]可能会非常大,所以在相加过程中对k取模判断
if(f[i]%k==0){
ans=i;
break;
}
}
cout<<((n%mod)*(ans%mod))%mod<<endl;
}