作者留言

晚上8:40终于AK了

今天非常幸运，所有题都一遍过（有一个+1是freopen写错了）

食用此题解前须知

不要问为什么没有错因，问就是上午还没回来

T1T1-T3T3

思路：水题，略。（ 20 min 内不 ACAC 都对不起自己）

代码：

T1

//num
#include <bits/stdc++.h>
using namespace std;
int a[1000];
int main(){
    freopen("num.in","r",stdin);
    freopen("num.out","w",stdout);
    int n;
    cin >> n;
    for(int i=1;i<=n;i++){
        cin >> a[i];
    }
    sort(a+1,a+n+1);
    for(int i=1;i<=n;i++){
        if(a[i]-a[1]+1!=i){cout << a[i]-1;break;}
    }
}

T2

//score
#include <bits/stdc++.h>
using namespace std;
int main(){
    freopen("score.in","r",stdin);
    freopen("score.out","w",stdout);
    int n,p;
    cin >> n >> p;
    int cnt=0;
    for(int i=1;i<=n;i++){
        int x;
        cin >> x;
        if(x<p) cnt++;
    }
    cout << cnt;
}

T3

#include <bits/stdc++.h>
#define int long long
using namespace std;
int a[1000];
auto sq(auto x){
    return x*x;
}
signed main(){
    freopen("jihui.in","r",stdin);
    freopen("jihui.out","w",stdout);
    int n;
    cin >> n;
    for(int i=1;i<=n;i++){
        cin >> a[i];
    }
    int mn=1e18;
    for(int i=1;i<=100;i++){
        int sum=0;
        for(int j=1;j<=n;j++){
            sum+=sq(a[j]-i);
        }
        mn=min(mn,sum);
    }
    cout << mn;
}

T4T4

思路： 1.基础前缀和，略。

2.哈希表优化：

(1) 用哈希表 cnt(mp也可) 记录前缀和出现的次数。

(2) 遍历数组时，维护当前前缀和 sum，查询 sum-k 的出现次数并累加到结果中。

(3) 同时更新 cnt[sum]，确保只统计当前元素之前的前缀和。

什么？你听不懂为什么要这么记录？OKOK，请看VCR：（AC选手可跳过）

我们需要快速找到满足 s[j]-s[i-1]==k 的 (i,j) 对数量。

转换一下公式：s[i-1]==s[j]-k。

因此，我们可以用哈希表记录每个前缀和出现的次数，在遍历过程中直接查询 s[j]-k 的出现次数。

懂了吗？Look my eyes，回答我！ 懂了就开始下一步。

3.初始化处理：

cnt[0]=1，处理从下标 0 开始的子数组（如第一个元素即为 k 的情况）

代码：

#include <bits/stdc++.h>
#define int long long
using namespace std;
unordered_map<int,int> cnt;
signed main(){
	freopen("tjqj.in","r",stdin);
	freopen("tjqj.out","w",stdout);
    int n,k;
    cin >> n >> k;
    int sum=0;
    int res=0;
    cnt[0]=1;
    for(int i=0;i<n;i++){
        int x;
        cin >> x;
        sum+=x;
        res+=cnt[sum-k];
        cnt[sum]++;
    }
    cout << res;
    return 0;
}

T5T5

思路：建图+BFS，毫无含金量 （大模拟）

建图方法见代码，不用邻接表和邻接矩阵。

代码：

#include <bits/stdc++.h>
using namespace std;
int main(){
    freopen("lx.in","r",stdin);
    freopen("lx.out","w",stdout);
	int n,m;
	cin >> n >> m;
	vector<vector<int> > vcr(n+1);
    while(m--){
        int a1,b1;
		cin >> a1 >> b1;
        vcr[a1].push_back(b1);
    }
    int res=0;
    for(int i=1;i<=n;i++){
        vector<bool> vis(n+1);
        queue<int> q{{i}};
        vis[i]=1;
        int cnt=0;
        while(q.size()){
            int now=q.front();
            q.pop();
            cnt++;
            for(int it:vcr[now]){
                if(!vis[it]){
                    vis[it]=1;
                    q.push(it);
                }
            }
        }
        res+=cnt;
    }
    cout << res << endl;
    return 0;
}

T6T6

很幸运的一遍过了

思路：

DPDP

注：本代码中用i代替k,用it代替x,用k代替r,用f代替dp,itmod表示x%k的值。（相应的，一些变量名也发生了变化）

1.状态表示：dp[j][r] 表示恰好选择 j 个元素，且这些元素的和模 k 等于 r 的子集数目。（k 被滚动数组 吃了 优化掉了）（这也是j逆向循环的原因，具体请参考01背包）

2.初始化：dp[0][0]=1（选择 0 个元素，和为 0，模 k 自然为 0）。

3.状态计算：对于每个元素 x，考虑是否将其加入当前子集：

不选：状态不变。

选：从 dp[j][r] 转移到 dp[j+1][(r+x)%k]（代码中使用 x%k 是为了优化性能）。

原理 这都不懂？：

因为如果将 x 加入当前子集，会导致两个变化：

(1).子集的元素个数从 j 变为 j+1。

(2).子集的和模 k 从 r 变为 (r+x)%k。

所以才要从 dp[j][r] 转移到 dp[j+1][(r+x)%k]。

4.结果：对于每个 k，累加 dp[k][0]（即选择 k 个元素且和模 k 为 0 的子集数目）。

代码：

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int mod=998244353;
signed main(){
    freopen("hate.in","r",stdin);
	freopen("hate.out","w",stdout);
    int n;
	cin >> n;
    vector<int> a(n);
    for(int& it:a) cin >> it;
    int res=0;
    for(int i=1;i<=n;i++){
        vector<vector<int>> f(i+1,vector<int>(i,0));
        f[0][0]=1;
        for(int it:a){
            int itmod=it%i;
            for(int j=i-1;j>=0;j--){
                for(int k=0;k<i;k++){
                    if(!f[j][k]) continue;
                    int nj=j+1,nk=(k+itmod)%i;
                    f[nj][nk]=(f[nj][nk]+f[j][k])%mod;
                }
            }
        }
        res=(res+f[i][0])%mod;
    }
    cout << res << endl;
    return 0;
}

T7T7

非常好，又是一遍过

思路： 题目要求按顺序移除顶点 1,2,...,N1,2,...,N ，每次移除后计算剩余图的连通分量数目。直接模拟这个过程会非常低效，因为每次移除顶点后需要重新计算连通分量，时间复杂度高达 O(N2)O(N^2)，对于 N<=2×105N<=2×10^5 的数据规模显然不可行。

与其模拟顶点的移除过程，不如考虑逆向操作：从空图开始，按相反顺序添加顶点。具体来说：

1.从顶点 NN 开始，逐步添加顶点 N,N−1,...,1N,N-1,...,1 。

2.每次添加一个顶点时，同时添加该顶点与已添加顶点之间的边。

3.使用并查集动态维护连通分量的数目。

这种逆向处理的优势在于：每次添加顶点时，所有可能与它相连的顶点都已经在图中，避免了直接模拟移除过程时需要频繁重新计算连通分量的问题。

代码：

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
int p[N],r[N];
vector<int> mp[N];
int find(int x){
    if(p[x]!=x)p[x]=find(p[x]);
    return p[x];
}
int main(){
    freopen("break.in","r",stdin);
    freopen("break.out","w",stdout);
    int n,m;
    cin >> n >> m;
    for(int i=0;i<m;i++){
        int a,b;
        cin>>a>>b;
        mp[a].push_back(b);
    }
    fill(p,p+N,-1);
    fill(r,r+N,0);
    vector<int> ans(n+1);
    ans[n]=0;
    int cnt=0;
    for(int x=n;x>=1;x--){
        p[x]=x;
        r[x]=1;
        cnt++;
        for(int b:mp[x])
            if(p[b]!=-1){
                int fix=find(x),fib=find(b);
                if(fix!=fib){
                    if(r[fix]>r[fib]) swap(fix,fib);
                    p[fix]=fib;
                    if(r[fix]==r[fib]) r[fib]++;
                    cnt--;
                }
            }
        ans[x-1]=cnt;
    }
    for(int i=1;i<=n;i++)
        cout << ans[i] << endl;
    return 0;
}
  1. Language
  2. 兼容模式
  3. 主题
  3. Worker 0, 15ms
  4. Powered by Hydro v5.0.0-beta.13 Community