从这一篇开始，比较重要的题目我会把题面放上
A. Politics
傻逼题目，傻逼题面，傻逼出题人
明明一句话能说清楚的事情为啥放样例了说啊？
不然你说这个东西有多项式解法吗？
一句话题解，和我不同意见的，都得死
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define ld long double
#define inf 0x7ffffff
using namespace std;
void solve(){
int n, k ,a[200];
cin >> n >> k;
string str[200];
for(int i=1;i<=n;++i)a[i]=1;
for(int i=1;i<=n;++i)
cin >> str[i];
for(int i=1;i<=k;++i)
for(int j=2;j<=n;++j)
if(str[j][i-1]!=str[1][i-1])
a[j]=0;
int sum=0;
for(int i=1;i<=n;++i)
sum+=a[i];
cout << sum << endl;
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
int t;
cin >> t;
while(t--){solve();}
return 0;
}
B. Indivisible
我写这题大概用了 3min ……
猜结论，这种排列类问题一般是与奇偶性有关的
看样例就出结论了：
- 大于 1 的奇数无解
- 偶数和 1 有解
证明不会，什么时候想出来什么时候写
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define ld long double
#define inf 0x7ffffff
using namespace std;
void solve(){
int n;
cin >> n;
if(n==1){
cout << 1 << endl;
return ;
}
if(n&1) {
cout << "-1" << endl;
return ;
}
for(int i=1;i<=n;i+=2){
cout << i+1 << " " << i << " ";
}cout << endl;
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
int t;
cin >> t;
while(t--){
solve();
}
return 0;
}
C. Almost Increasing Subsequence
定义几乎上升区间为对于区间内任意三个连续元素\(x,y,z\)，不存在\(x\geq y \geq z\)
给带数组 \(a\) ，多组询问，求出区间 \([l,r]\) 内的最长的几乎上升序列的长度
\(n,q\in [1,2e5],\,a_i\in[1,1e9]\)
果然一道题对于我和 zmy 真就是一个天上一个地下啊
明显，连续选一段严格上升子区间是一定合法的，整个数列会被划分为不同的上升序列，我们相邻的上升序列只能选边界上的，内部的不能选
(我一开始想的是分成上升和下降来做，但是那样就过于麻烦了)
当 \(l,r\) 是内部节点的时候，是可以选上的
使用前缀和进行计算
所以做完了
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define ld long double
#define inf 0x7ffffff
#define pii pair<int,int>
using namespace std;
const int maxN=2*1e5+10;
int n,q;
int a[maxN],pre[maxN],vis[maxN];
signed main(){
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
cin >> n >> q;
for(int i=1;i<=n;++i) cin >> a[i];
for(int i=2;i<n;++i){
pre[i]+=pre[i-1];
if(a[i]>=a[i+1]&&a[i]<=a[i-1]) pre[i]++,vis[i]=1; //在其内部，不增
}
pre[n]=pre[n-1];
while(q--){
int l,r;
cin >> l >> r;
int ans=r-l+1-pre[r]+pre[l-1];
ans+=vis[r]+vis[l];
cout << min(ans,r-l+1) << endl;
}
return 0;
}
D. Fish Graph
定义一个点数为 \(k\) 的无向图为鱼图当且仅当图上有\(k-2\) 个节点都仅在同一个环上，而且有一个节点有两条边向外连向两个不在环上的节点
给你一个 \(n\) 个点 \(m\) 条边的图，判定其是否有一个子图为鱼图，存在则输出鱼图的边集
\(n,m\in [1,2000]\)
这里明显，有鱼图的充要条件是其有一个点在环上且这个点的度数至少为 4
接下来就是代码实现了，一开始我写了个线性的解法，但有 114514 个细节，没调出来，所以这里用的是 \(O(n^2)\) 的解法
对于每一个点，dfs判断其是否在环上，若有满足要的节点，则强行 dfs 找出环来
实际上，我们把一个节点定位 DFS 树的根，则经过这个节点的环一定是以当前节点为端点的，所以记录一下父亲就可以了
把第一个 dfs 换成 DFS 树可以做到线性，但我没调出来
代码十分好写
#include <cstdio>
#include <cmath>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#include <vector>
#include <map>
#include <unordered_map>
#include <set>
#define ll long long
#define fp(a,b,c) for(ll a=b;a<=c;a++)
#define fd(a,b,c) for(ll a=b;a>=c;a--)
#define pii pair<int,int>
#define pll pair<ll,ll>
#define fr first
#define sd second
#define mod 1000000007
#define inf 0x3f3f3f3f
using namespace std;
const int maxN=2000+10;
int n,m,root;
int low[maxN],dfn[maxN],idx,deg[maxN],cur[maxN],in[maxN],vis[maxN],fa[maxN],flag;
vector<int> g[maxN];
vector<pii> ans;
inline int rd(){
int x = 0, f = 1;char ch = getchar();
while(ch < '0' || ch > '9'){if(ch == '-')f = -1;ch = getchar();}
while(ch >= '0' && ch <= '9')x = (x<<1) + (x<<3) + (ch^48),ch = getchar();
return x * f;}
inline ll lrd(){
ll x = 0, f = 1;char ch = getchar();
while(ch < '0' || ch > '9'){if(ch == '-')f = -1;ch = getchar();}
while(ch >= '0' && ch <= '9')x = (x<<1) + (x<<3) + (ch^48),ch = getchar();
return x * f;}
void circle(int now,int f){
dfn[now]=++idx;
for(int x:g[now]){
if(x==f) continue;
if(!dfn[x]) circle(x,now);
if(x==root) in[root]=1;
}
}
void dfs(int now,int f){
fa[now]=f;
dfn[now]=++idx;
for(int x:g[now]){
if(x==f) continue ;
if(flag) return ;
if(x==root){
int cur=now;
while(fa[cur]!=cur){
ans.push_back({cur,fa[cur]});
vis[cur]=1,vis[fa[cur]]=1;
cur=fa[cur];
}ans.push_back({now,root});
flag=1;
return ;
}
}
for(int x:g[now])
if(!dfn[x]) dfs(x,now);
}
void clearit(){
fp(i,1,n) deg[i]=cur[i]=low[i]=vis[i]=dfn[i]=in[i]=fa[i]=0,g[i].clear();
ans.clear(),flag=0;
}
void solve(){
n=rd(),m=rd();
fp(i,1,m){
int u,v;
u=rd(),v=rd();
if(u==v) continue ;
g[u].push_back(v);
g[v].push_back(u);
++deg[u],++deg[v];
}
fp(i,1,n){
root=i,circle(i,i);
idx=0;
memset(dfn,0,sizeof(dfn));
}
fp(i,1,n){
if(deg[i]>3&&in[i]){
cout << "Yes" << endl;
root=i;
dfs(i,i);
int sum=0;
for(int x:g[root]){
if(!vis[x]) ans.push_back({root,x}),++sum;
if(sum==2) break;
}
cout << ans.size() << endl;
for(pii x:ans) cout << x.fr << " "<< x.sd << endl;
clearit();
return ;
}
}
cout << "No" << endl;
clearit();
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
int t;
t=rd();
while(t--){
solve();
}
return 0;
}