A. 小田的消消乐游戏

难度：⭐

思路

有2种情况：

（1）首尾相同，直接输出1。

（2）首尾不同，去找一个ii,满足ai==a1a_i==a_1&&ai+1==ana_{i+1}==a_n,也就是第ii个数可以与第一个数一起消除第一段，第i+1i+1个数可以与第一个数一起消除第二段。

如果n≤3n≤3,还要特判一下。

代码

#include<bits/stdc++.h>
using namespace std;
int a[500005];
int n;
int cmp(){
    if(n<=3){
        if(n==1){
            return -1;
        }else{
            if(a[1]!=a[n]){
                return -1;
            }
            return 1;
        }
    }
    if(a[1]==a[n]){
        return 1;
    }
    for(int i=3;i<n;i++){
        if(a[i]==a[n]&&a[i-1]==a[1]){
            return 2;
        }
    }
    return -1;
}
int main(){
    freopen("num.in", "r", stdin);
    freopen("num.out", "w", stdout);
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    cout<<cmp();
    return 0;
}

要点

  • 虽然AC了，但是做题的过程中还是有点猴急，稳住心态最重要❤️
  • 前几十分钟都没有想到从这个角度分类讨论，应该事先把讨论角度列出，然后分类讨论，有条不紊，效率更高📝

B.小田的气球爆炸啦

难度：⭐⭐

思路

有3种情况：

（1）n==2n==2&&a1==a2a_1==a_2,一山不容二虎，直接抵消，谁也活不了，结果为0。

（2）ai≥a1+a2+...+ai−1+ai+1+...+an−1+ana_i≥a_1+a_2+...+a_{i-1}+a_{i+1}+...+a_{n-1}+a_n,aia_i可以抵消所有气球，只有a1a_1是最后的赢家，结果为1.

（3）大家差别不大，实力相当，怎么办？列草稿啊！

第一组

a={2,2,2,2}a=\{2,2,2,2\}

先看a1a_1,剩下的气球可以分成三组：{a2,a3},{a3,a4},{a2,a4}\{a_2,a_3\}, \{a_3,a_4\},\{a_2,a_4\}气球们自相残杀互相抵消，a1a_1在旁边吃瓜这组数据中可能是剩下的。a2,a3,a4a_2,a_3,a_4同理。结果为4.

第二组

a={1,1,3,1,4}a=\{1,1,3,1,4\}

先看a1a_1,剩下的气球不管是各杀各的互相抵消，还是强强联手，对抗a5气球一起抵消a5a_5,都会剩下至少一个，a1a_1活不了，a2,a4a_2,a_4也一样。

再看a3a_3,剩下的气球强强联手，对抗a5气球一起抵消a5a_5,会剩下一个气球，a3a_3再来抵消这一个， a[3]得以幸存，a5a_5比a4a_4大，也一样能活。结果为2。

第三组

a={1,2,3,4,5}a=\{1,2,3,4,5\}

先看a1a_1,剩下的气球先让a4a_4和a5a_5抵消，剩下一个。a2a_2和a3a_3抵消，剩下一个，然后和刚才的一个抵消。a1a_1可能会剩下。其他的都比a1a_1大，也可以，结果为5。

  • 这里有一个问题出现了：同样是1，为什么第二组不能留下，而第三组可以？

我们来比较一下，似乎每一组最优抵消都只会剩下一个或者不剩。我们再来分类讨论，分别找一找两类结果的抵消数据的共同点：

抵消结果为1的数据：{1,3,1,4},{1,1,1,4},{2,3,4,5},{1,2,3,5}\{1,3,1,4\},\{1,1,1,4\},\{2,3,4,5\},\{1,2,3,5\}

抵消结果为0的数据：$\{2,2,2\},\{1,1,1,3\},\{1,3,4,5\},\{1,2,4,5\},\{1,2,3,4\}$

发现了吗？抵消结果是与数据和对2的取模。

那我们就可以从奇偶性入手，由此可得：

若aa的总和是奇数，则有：

设aa的总和为ss。

设aia_i为奇数，那么s−ais-a_i为偶数，抵消结果是0。

设aia_i为偶数，那么s−ais-a_i为奇数，抵消结果是1。

这道题输入最小的偶数是2,2>12,2>1,所以若aa的总和是奇数，结果为nn。

反之，则有：

设aa的总和为ss。

设aia_i为偶数，那么s−ais-a_i为偶数，抵消结果是0。

设aia_i为奇数，那么s−ais-a_i为奇数，抵消结果是1。

这道题输入最小的奇数是1,1−1=01,1-1=0,直接蒸发，所以还要有统计大于一的数的个数cntcnt。若aa的总和是偶数，结果为cntcnt。

代码

#include<bits/stdc++.h>
using namespace std;
long long a[100005];
int main(){
    freopen("balloon.in", "r", stdin);
    freopen("balloon.out", "w", stdout);
    long long n,mx=0,cnt=0;
    cin>>n;
    long long s=0;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        s+=a[i];
        mx=max(mx,a[i]);
        if(a[i]>1){
            cnt++;
        }
    }
    if(n==2&&a[1]==a[2]){
        cout<<0;
    }else if(mx>=s-mx){
        cout<<1;
    }else if(s%2==1){
     
        cout<<n;
    }else{
        cout<<cnt;
    }
    return 0;
}

要点

  • 虽然拿部分分了，但是做题的过程中还是没有想到第一点和第二点，第三点也没有深入想。思考的时候，应该向DFS学习：“一个点想到底，想完再想其他角度”🧐

小k的加减游戏

难度：⭐

思路

及其淼的一道题，用贪心思想，拿大的数减一，拿小的数加一。

代码

#include<bits/stdc++.h>
using namespace std;
int a[5];
string ans;
int main(){
    freopen("game.in", "r", stdin);
    freopen("game.out", "w", stdout);
    int n,f=1;
    cin>>n>>a[0]>>a[1]>>a[2];
    while(n--){
        string op;
        cin>>op;
        int x=op[0]-'A',y=op[1]-'A';
        if(a[x]>a[y]){
            a[x]--;
            a[y]++;
            ans+=op[1];
        }else{
            a[y]--;
            a[x]++;
            ans+=op[0];
        }
        if(a[x]==-1||a[y]==-1){
            f=0;
        }
    }
    if(f==0){
        cout<<"No";
    }else{
        cout<<"Yes"<<endl;
        for(int i=0;i<ans.size();i++){
            cout<<ans[i]<<endl;
        }
    }
    return 0;
}

要点

  • 虽然AC了，但是做题的过程中还是想复杂了，应该尽量简单📏

D .蓬莱山仙峰台

难度：⭐

思路

有2种思路：

（1）数组标记法。根据福尔摩斯的名言：排除所有不可能之后剩下的那个就是真相。我们把所有可以确定不是仙峰台的观景台都标记起来，剩下的就是仙峰台。

（2）邻接表遍历法。把图用邻接表储存起来，每一个观景台单独遍历与其相连的观景台，比较大小，每一个都执行一次，就可以找到所有仙峰台。

代码

（数组标记法）

#include<bits/stdc++.h>
using namespace std;
int a[100005];
int vis[100005];
int main(){
    freopen("penglai.in", "r", stdin);
    freopen("penglai.out", "w", stdout);
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    while(m--){
        int x,y;
        cin>>x>>y;
        if(a[x]<a[y]){
            vis[x]=1;
        }else if(a[y]<a[x]){
            vis[y]=1;
        }else{
            vis[x]=1;
            vis[y]=1;
        }
    }
    int sum=0;
    for(int i=1;i<=n;i++){
        if(vis[i]==0){
            sum++;
        }
    }
    cout<<sum;
    return 0;
}

（邻接表遍历法）

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5+5, M = N*2;
int h[N],e[M],ne[M],idx,n,m,st[N];
void add(int a, int b) {
	e[idx] = b; 
	ne[idx] = h[a];  
	h[a] = idx;
    idx++;
}
int a[N];
bool cmp(int i){
    if(h[i]==-1){
        return 1;
    }
    for(int j=h[i];j!=-1;j=ne[j]) {
        if(a[i]<=a[e[j]]){
            return 0;
        }
    }
    return 1;
}
int main() {
    freopen("penglai.in", "r", stdin);
    freopen("penglai.out", "w", stdout);
	cin >> n>>m;
	memset(h, -1, sizeof h);
    for (int i=1; i<=n; i++) {
		cin>>a[i];
	}
	for (int i=1; i<=m; i++) {
		int x,y; 
		cin >>x>> y;
		add(x,y);
		add(y,x);
	}
    
    int ans=0;
	for (int i=1;i<=n; i++) {
		ans+=cmp(i);
	}
    cout<<ans;
    return 0;
}

要点

  • 虽然AC了，但是做题的过程中没有想到邻接表遍历法，应该多想📄

E.数学题1

难度：⭐⭐⭐

思路

a+ba+b是b⋅gcd(a,b)b·gcd(a,b)的倍数

a=x⋅ba=x·b

gcd(a,b)=bgcd(a,b)=b

a+ba+b是b∗bb*b的倍数

循环查找即可。

代码

#include<bits/stdc++.h>
using namespace std;
int main(){
    freopen("math1.in", "r", stdin);
    freopen("math1.out", "w", stdout);
    int n,m,l=0;
    cin>>n>>m;
    for(long long b=1;b<=m;b++){
        for(long long a=b;a<=n;a+=b){
            if((a+b)%(b*b)==0){
                l++;
            }
        }
    }
    cout<<l;
    return 0;
}

要点

  • 看到题目只想到了找规律，没有想到推公式➗

F.小z的徒步旅行

难度：⭐⭐⭐

思路

纯暴搜必定超时，所以需要DP来解。

从一个小木屋ii到另一个小木屋jj有多少条路呢？（不考虑长短）当然是(li+si)⋅(lj+sj)(l_i+s_i)·(l_j+s_j)条，那不可以走的有多少条路？当然是li⋅ljl_i·l_j条。那么可以走的路线就是(li+si)⋅(lj+sj)−li⋅lj(l_i+s_i)·(l_j+s_j)-l_i·l_j条，用rr数组来统计长短路线和，那就是ri⋅rj−li⋅ljr_i·r_j-l_i·l_j条。

开一个f数组，fi,jf_{i,j}表示第ii天在第jj个小木屋有多少种方案，假设第ii天在第jj个小木屋,i−1i-1天在第kk个小木屋，那么就有(rj⋅rk−lj⋅lk)⋅fi−1,k(r_j·r_k-l_j·l_k)·f_{i-1,k}种方案，由于前一天并不确定在哪一个小木屋，所以要循环求和。

算的过程中可能会数据溢出，应该在各个地方加上取模处理。

代码

#include<bits/stdc++.h>
using namespace std;
const int Mod=1e9+7;
long long l[110],s[110],r[110],f[1010][110];
int main(){
    freopen("walk.in", "r", stdin);
    freopen("walk.out", "w", stdout);
    int n,m;
    cin>>m>>n;
    for(int i=1;i<=m;i++){
        cin>>s[i];
        r[i]=s[i];
    }
    for(int i=1;i<=m;i++){
        cin>>l[i];
        r[i]+=l[i];
     }
    f[0][1]=1;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            long long sum=0;
            for(int k=1;k<=m;k++){
                sum+=(((r[j]*r[k]-l[j]*l[k])%Mod)*f[i-1][k]%Mod)%Mod;
                sum%=Mod;
            }
            f[i][j]=sum;
        }
    }
    int sum=0;
    for(int i=1;i<=m;i++){
        sum=(sum%Mod+f[n][i])%Mod;
    }
    cout<<sum;
    return 0;
}

要点

  • 做的时候看到直接放弃，但复现赛写的时候却一下就过了，思路也很简单，骗分也很容易，不应该看一眼就放弃🙋‍♂️
  1. Language
  2. 兼容模式
  3. 主题
  3. Worker 0, 43ms
  4. Powered by Hydro v5.0.0-beta.13 Community