[TOC]
2023ECJTU校赛题解
A. FF 想吃糖果
解题思路
题意：给一副无向图，问你最少删除多少个点，且这些不是度最多的点，使得这幅图不连通？
本题两个难点：
1、最小割删边转化删点。
2、不能删掉度最多的点。
首先先不考虑 FF 的技能，先思考这个问题，最少删多少个点使得图不连通？
那么这个题就是一个最小割问题。但是最小割是删除边使得图不连通，而这个题考虑的是点，所以不能直接乱搞。
那么这样需要一个小技巧，割边转割点，因此我们需要拆点。
即把一个点拆成两个点，中间连一条边权为 的边。
前一个点作为“入点”，别的点连边连入这里。
后一个点作为“出点”，出去的边从这里出去。
这样，只要我们切断中间那条边，就可以等效于除去这个点了。
以下图（借别人大佬的，侵权联系删除）举例：
红色的边边权为 ，黑色的边边权为
，原点和汇点的内部边权为
，因为显然这两个点不能删除。
然后我们需要考虑 FF 的技能，FF 会保护联系最多的人，无法删除这些点。如何处理？
考虑那些点入边直接连到出边对应的点。
但是，这样太麻烦了。
因为，首先要存进入的点的编号，还要存出去的点的编号，之后两层循环相连，你以为这就完了？这样的点不止一个，所以你还得多次操作。不建议这么写。
那么这里也有一个小技巧，我们将拆掉的点中间的权值改成 就好了，以上图为例子：
这样就完美地解决了这个问题。
或者重新加一条边，权值为 也行。
注意是除了 FF 和 pld 之外联系最多的！
然后只要求一个最小割就好了，利用最大流最小割定理，跑一遍 dinic 就可以通过了。
AC_Code
- C/C++
#include<iostream>
#include<algorithm>
#include<string.h>
#include<string>
#include<vector>
#include<queue>
#include<set>
#include<map>
#define int long long
#define fi first
#define se second
#define inf 0x3f3f3f3f
#define INF 1e18
using namespace std;
typedef pair<int, int> PII;
const int N = 3e6 + 10, M = N * 2, Mod = 1e9 + 7;
int n, m, S, T, ans;
int e[M], ne[M], f[M], h[N], idx;
int q[N], cur[N], d[N];
int st[N], g[1010][1010];
int din[N], mxd;
void add(int a, int b, int c)
{
e[idx] = b, ne[idx] = h[a], f[idx] = c, h[a] = idx++;
e[idx] = a, ne[idx] = h[b], f[idx] = 0, h[b] = idx++;
}
bool bfs()
{
memset(d, -1, sizeof(d));
int hh = 0, tt = 0;
q[0] = S, d[S] = 0, cur[S] = h[S];
while(hh <= tt)
{
int t = q[hh++];
for(int i = h[t]; ~i; i = ne[i])
{
int ver = e[i];
if(d[ver] == -1 && f[i])
{
cur[ver] = h[ver];
d[ver] = d[t] + 1;
if(ver == T) return true;
q[++tt] = ver;
}
}
}
return false;
}
int find(int u, int limit)
{
if(u == T) return limit;
int flow = 0;
for(int i = cur[u]; ~i && flow < limit; i = ne[i])
{
cur[u] = i;
int ver = e[i];
if(d[ver] == d[u] + 1 && f[i])
{
int t = find(ver, min(f[i], limit - flow));
if(!t) d[ver] = -1;
f[i] -= t, f[i ^ 1] += t, flow += t;
}
}
return flow;
}
int dinic()
{
int r = 0, flow;
while(bfs()) while(flow = find(S, inf)) r += flow;
return r;
}
void solve()
{
cin >> n;
S = 1, T = n;
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++)
cin >> g[i][j];
memset(h, -1, sizeof(h));
for(int i = 1; i <= n; i++)
{
st[i] = idx;
if(i == S || i == T) add(i, i + n, inf);
else add(i, i + n, 1);
}
for(int i = 1; i <= n; i++)
for(int j = 1; j < i; j++)
if(g[i][j])
{
add(i + n, j, inf), add(j + n, i, inf);
din[i]++, din[j]++;
}
for(int i = 2; i < n; i++) mxd = max(mxd, din[i]);
for(int i = 2; i < n; i++)
if(din[i] == mxd) f[st[i]] = inf;
int ans = dinic();
cout << (ans >= inf / 2? -1: ans) << endl;
}
signed main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int T = 1;
// cin >> T;
while(T--)
solve();
return 0;
}
B. 吃糖果
解题思路
假如我们求到了操作需要的最小次数，我们就可以知道能不能在不超过 k 次吃掉所有糖果。
设 dp[i][j] 是将 i 到 j 的糖果吃掉需要的最小次数，因为操作的性质是连续相同的字符，那么我们转移的时候可以考虑分这个区间首尾的字符是不是相同的，假如是相同的，那么 dp[i][j]=min(dp[i+1][j],dp[i][j-1])，因为区间最后两端的字符都是可以最后进行操作的，这并不会影响，我们可以理解为顺便把端点的糖果给吃了，所以转移的时候就不会增加权值。假如不是相同的，那么就只能分为两个区间来吃掉这个区间的糖果，然后枚举中间值，dp[i][j]=min(dp[i][j],dp[i][k],dp[k+1][j])。
但是这样会发现时间复杂度是 ，计算量似乎是
10 亿，但是这里需要注意，第三层循环只会枚举区间长度，然后最坏的情况计算量不会超过 2 亿，在常数很小的 dp 中足够。
AC_Code
- C/C++
//
// Created by liuhao.
//
#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3,"Ofast","inline")
#include<bits/stdc++.h>
using namespace std;
#define ios ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define vii vector<vector<int>>
signed main()
{
ios;
int t;
cin>>t;
while(t--)
{
int n,c;
cin>>n>>c;
string s;
cin>>s;
s=" "+s;
vii dp(n+1,vector<int>(n+1,0x3f3f3f3f));
for (int i = 1; i <= n; i++) {
dp[i][i]=1;
}
for(int len=2;len<=n;len++)
{
for(int i=1;len+i-1<=n;i++)
{
int j=len+i-1;
if(s[i]==s[j])dp[i][j]=min(dp[i+1][j],dp[i][j-1]);
else
{
for(int k=i;k<j;k++)
{
dp[i][j]=min(dp[i][k]+dp[k+1][j],dp[i][j]);
}
}
}
}
cout<<(dp[1][n]<=c?"YES":"NO")<<endl;
}
return 0;
}
C. FF 爱吃糖
解题思路
1、只要考虑每颗糖果的 happy 值模上 的结果。
2、对于 happy 值为 的糖果，模上
的结果为
，证明如下：
3、思考拿的糖果满足什么条件才能使得剩余糖果的总价值模上 的结果不变：拿的糖果的总价值是
的倍数。
4、根据上面三点，我们可以得知答案就是：从 颗糖果中选择若干个，总
happy 值为 的倍数的方案数。
5、总 happy 值为 的倍数等价于：总
happy 值 。
6、我们考虑 ：定义
表示从前
颗糖中选，总
值模上
的结果为
的方案数。
根据第 颗糖果选与不选对集合进行划分：
不选第 颗糖果的方案数为
选第 颗糖果的方案数为
所以
7、答案为 。
AC_Code
- C/C++
#include<bits/stdc++.h>
using namespace std;
const int N = 5010, mod = 1e9 + 7;
int f[N][N];
int a[N];
int n,p;
string s;
signed main()
{
cin >> n >> p;
for(int i=1; i<=n; i++)
{
cin >> a[i] >> s;
}
f[0][0] = 1;
for(int i=1; i<=n; i++)
{
for(int j=0; j<p-1; j++)
{
f[i][j] = f[i-1][j] + f[i-1][((j-a[i]) % (p-1) + (p-1))%(p-1)];
f[i][j] %= mod;
}
}
cout << f[n][0];
}
D. FF 分糖果
题解
解题思路，我们可以将小朋友的编号和要求视为有向图。
小朋友代表节点，小朋友的要求代表有向边，小朋友 想比小朋友
多
个糖果相当于添加一条有向边：从
到
的边，权重为
。
根据题目要求，我们只需要了解各个小朋友之间的糖果关系即可，可以根据上面的建图思想，用带权的并查集解决。
我们可以认定答案初始值为总要求 ，遇到不合法的要求，即不合法的关系，答案就减一，最后输出答案。
AC_Code
- C/C++
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+10;
int d[N],p[N];
int find(int x)
{
if(x!=p[x])
{
int root=find(p[x]);
d[x]+=d[p[x]];
p[x]=root;
}
return p[x];
}
void solve()
{
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++)
{
p[i]=i;
d[i]=0;
}
int ans=m;
while(m--)
{
int a,b,dis;
cin>>a>>b>>dis;
int x=find(a),y=find(b);
if(x!=y)
{
d[x]=dis-d[a]+d[b];
p[x]=y;
}
else{
if(dis!=d[a]-d[b]) ans--;
}
}
cout<<ans<<'\n';
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr),cout.tie(nullptr);
int t;
cin>>t;
while(t--)
{
solve();
}
return 0;
}
E. 美味的果实
解题思路
先判断第一次结果是否在假期后，是的话假期内结果天数为 ，否则计算剩余天数除结果周期即为剩余假期结果天数，再加上第一天即为答案。
AC_Code
- C/C++
#include<iostream>
using namespace std;
int main()
{
int n,m,p;
cin>>n>>m>>p;
if(m>n)cout<<0;
else cout<<1+(n-m)/p;
return 0;
}
F. 贪玩的 FF
解题思路
求一个区间中两两消除后个数不超过一个，即数量为奇数个的数不超过 个。由于
，考虑将每一个数变成
，于是我们可以得到一个新的序列
，于是区间
满足 Link-Delete 的条件就变成了
^
^
^
为
的整数次幂。
考虑维护一个前缀异或数组 ，于是问题就变成了求区间
中有多少对
满足
^
为
的整数次幂。由于此题为没有修改操作，使用离线算法莫队维护，提前将序列中的每一个数对应的答案预处理出来最多为
个，莫队每次修改的时候统计答案， 时间复杂度
。
AC_Code
- C/C++
#include<bits/stdc++.h>
using namespace std;
using i64 = long long;
const int N = 1e5 + 10;
unordered_map<int,int> mp; //离散化
int cnt[N];
int blk[N],s[N];
vector<vector<int>> f;
int n,m;
struct node{
int l,r,id;
bool operator <(const node&a) const{
if(blk[this->l] == blk[a.l])return this->r < a.r;
return blk[this->l] < blk[a.l];
}
}ask[N];
void upt(int p,int v,i64 &res){ //更新操作，每次修改的时候查询区间中满足条件的个数
if(v == 1){
for(auto x : f[p]){
res += cnt[x];
}
cnt[mp[s[p]]] ++;
}
else{
cnt[mp[s[p]]] --;
for(auto x : f[p]){
res -= cnt[x];
}
}
}
int main()
{
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
cin >> n >> m;
int tt = 1;mp[0] = tt++;
for(int i = 1; i <= n; i++){
int x;
cin >> x;
s[i] = 1<<(x-1),s[i] ^= s[i-1];
if(!mp.count(s[i]))mp[s[i]] = tt++;
}
f.resize(n+1);
for(int i = 0; i <= n; i++){
f[i].push_back(mp[s[i]]);
for(int j = 1; j < 31; j++){ //预处理所有满足条件的数
int x = s[i] ^ (1<<(j-1));
if(mp.count(x))f[i].push_back(mp[x]);
}
}
int len = sqrt(n),t = 1; //分块
for(int i = 1; i <= n; i++){
if(i > t*len)t++;
blk[i] = t;
}
for(int i = 1; i <= m; i++){
int l,r;
cin >> l >> r;
ask[i] = {l-1,r,i};
}
sort(ask+1,ask+1+m); //对询问进行排序
i64 res = 0;
int l = 0,r = -1;
vector<i64> ans(m+1);
for(int i = 1; i <= m; i++){ //莫队操作 模板
while(r > ask[i].r)upt(r--,-1,res);
while(r < ask[i].r)upt(++r,1,res);
while(l < ask[i].l)upt(l++,-1,res);
while(l > ask[i].l)upt(--l,1,res);
ans[ask[i].id] = res;
}
for(int i = 1; i <= m; i++)cout << ans[i] << "\n"; //输出答案
}
G. 小杰同学去旅游
解题思路
每次运输只有一个人递送校园卡即可。
当校园卡数目大于等于人数的时，所有人一次就进入校门，可以直接输出为 。
当校园卡数目小于或者等于一的时，只有一个人能进入，或者所有人都不能进入，直接输出为 。
其他情况，用 来记录一共几个来回，每一次只能帮助
个人进入校园，用
记录一共有多少个来回，到最后，如果
时，还有一小部分人没有进入校园，
再加一，最后计算所需要的时间，
为来回需要的次数，
表示加上第一次送入的所需要的时间。
AC_Code
#include<bits/stdc++.h>
#include <cmath>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#pragma GCC optimize(2)
#pragma GCC optimize(3,"Ofast","inline")
#define endl '\n'
#define pii pair<int,int>
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
const int maxn=1e6+5;
int main(){
int t;
cin>>t;
while(t--){
ll n,m,ans=0;
cin>>n>>m;
if(m>=n)cout<<1<<endl;
else if(m==1)cout<<-1<<endl;
else {
n-=m;
ans++;
ans+=n/(m-1)*2;
if(n%(m-1))ans+=2;
cout<<ans<<endl;
}
}
}
H. 偶遇
解题思路
本题给出一张无向连通图，我们首先要将这张图上的环全部缩为一个点，无向图的连通分量我们可以想到边双和点双，点双会将两个不构成环的点缩在一起，所以我们考虑边双。但是其实我们可以把无向图当成有向图搜，然后使用强连通分量版的 算法。
在缩完点之后，能否偶遇其实就是判断这两段路径是否相交，两段路径是否可以相交我们通过多画几张图就能看出，肯定存在其中一条路径的两个端点的最近公共祖先在另一条路径上，而判断一个点是否在一条路径上，我们可以看这个点到两端的距离加起来是否等于路径长度。而在树上我们可以通过 快速算出两点间的距离。
时间复杂度为 。
AC_Code
#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
const int N=1e5+10,M=1e6+10;
int hs[N],h[N],e[M],ne[M],idx;
void add(int h[],int a,int b){
e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
int n,m,q;
int dfn[N],low[N],timestamp;
int stk[N],top;
bool in_stk[N];
int scc_cnt,id[N];
int depth[N],fa[N][18];
void bfs(){
queue<int>q;
q.push(1);
memset(depth,0x3f,sizeof(depth));
depth[0]=0,depth[1]=1;
while(q.size()){
int t=q.front();
q.pop();
for(int i=hs[t];~i;i=ne[i]){
int j=e[i];
if(depth[j]>depth[t]+1){
depth[j]=depth[t]+1;
q.push(j);
fa[j][0]=t;
for(int k=1;k<=17;k++){
fa[j][k]=fa[fa[j][k-1]][k-1];
}
}
}
}
}
int lca(int a,int b){
if(depth[a]<depth[b])swap(a,b);
for(int k=17;k>=0;k--){
int t=fa[a][k];
if(depth[t]>=depth[b]){
a=t;
}
}
if(a==b)return a;
for(int k=17;k>=0;k--){
if(fa[a][k]!=fa[b][k]){
a=fa[a][k],b=fa[b][k];
}
}
return fa[a][0];
}
void tarjan(int u,int f){
dfn[u]=low[u]=++timestamp;
stk[++top]=u,in_stk[u]=true;
for(int i=h[u];~i;i=ne[i]){
int j=e[i];
if(j==f)continue;
if(!dfn[j]){
tarjan(j,u);
low[u]=min(low[u],low[j]);
}
else if(in_stk[j])low[u]=min(low[u],dfn[j]);
}
if(dfn[u]==low[u]){
int y;
scc_cnt++;
do{
y=stk[top--];
in_stk[y]=false;
id[y]=scc_cnt;
}while(y!=u);
}
}
int distance(int a,int b){
return depth[a]+depth[b]-2*depth[lca(a,b)];
}
int main(){
scanf("%d%d%d",&n,&m,&q);
memset(h,-1,sizeof(h));
while(m--){
int a,b;
scanf("%d%d",&a,&b);
add(h,a,b),add(h,b,a);
}
for(int i=1;i<=n;i++){
if(!dfn[i])tarjan(i,0);
}
memset(hs,-1,sizeof(hs));
for(int u=1;u<=n;u++){
for(int i=h[u];~i;i=ne[i]){
int j=e[i];
in***],b=id[j];
if(a!=b){
add(hs,a,b);
}
}
}
bfs();
while(q--){
int a,b,c,d;
scanf("%d%d%d%d",&a,&b,&c,&d);
int aa=id[a],bb=id[b],cc=id[c],dd=id[d];
int lca1=lca(aa,bb),lca2=lca(cc,dd);
if(distance(aa,bb)==distance(aa,lca2)+ distance(lca2,bb)){
printf("Yes\n");
continue;
}
if(distance(cc,dd)== distance(cc,lca1)+ distance(lca1,dd)){
printf("Yes\n");
continue;
}
printf("No\n");
}
return 0;
}
I. 序列·终
解题思路
由等差数列的求和公式：
我们第一个数为，第二个数为
。
则我们可以得到
所以我们可以通过枚举 的值的方式来计算个数，时间复杂度
AC_Code
- C++
#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
#include<vector>
#include<set>
#include<map>
#include<cmath>
using namespace std;
#define int long long
#define endl "\n"
const int N = 3e5+10;
int n,m,k;
void solve()
{
cin>>n;
int res=0;
n*=2;
for(int i = 1;i*i<=n;i ++ )//枚举(l+r)的所有情况。
{
if(n%i==0&&(i%2)!=(n/i)%2)res++;//判断是否存在(l+r)与(r-l+1),必须同奇或者同偶才能成立。
}
cout<<res*2<<endl;//有负数存在的情况所以要乘2。
}
signed main()
{
ios_base::sync_with_stdio(0); cin.tie(0);cout.tie(0);
int t=1;
while(t--)
{
solve();
}
return 0;
}
京公网安备 11010502036488号