Codeforces Round 993 (Div. 4)题解

A. Easy Problem

思路：经过看了一眼，我们发现，a+b的和一定是n，且两个都是正整数，

所以a的范围就是从1~n-1 

所以输出n-1即可

#include<bits/stdc++.h>
using namespace std;
#define int long long
int t;
int n,k;
int a,b;
string s; 
void solve()
{cin>>n;cout<<n-1<<"\n";
}signed main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);cin>>t;while(t--)solve();return 0;
}

B. Normal Problem

思路：稍加思索一下就发现，其实从里面看的话，就是将字符串翻转之后，将p变成q，将q变成p

#include<bits/stdc++.h>
using namespace std;
#define int long long
int t;
int n,k;
int a,b;
string s; 
void solve()
{cin>>s;for(int i=0;i<s.size();i++){if(s[i]=='p'){s[i]='q';}else if(s[i]=='q'){s[i]='p';}}reverse(s.begin(),s.end());cout<<s<<"\n";
}signed main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);cin>>t;while(t--)solve();return 0;
}

 C. Hard Problem

思路：第一排尽量都坐满a,第二排尽量坐满b，然后空的用c补全，直到座位为0，或者c没有了

#include<bits/stdc++.h>
using namespace std;
#define int long long
int t;
int n,k;
int a,b,c;
string s; 
void solve()
{cin>>n>>a>>b>>c;int ans=0;cout<<min(a,n)+min(b,n)+min(c,max(n-a,0LL)+max(n-b,0LL))<<"\n";
}signed main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);cin>>t;while(t--)solve();return 0;
}

 D. Harder Problem

思路：我们有n个位置放数，那我们就按照123...n这种情况放数，这样每个数只出现一次，都可以作为模数，但是，要注意数出现的顺序，所以我们出现一个新的就输出当前这个数，然后遍历1~n看哪个数还没出现过，没出现则输出

#include<bits/stdc++.h>
using namespace std;
#define int long long
int t;
int n,k;
int a[200005];
void solve()
{cin>>n;int vis[200005];memset(vis,0,sizeof(vis));for(int i=1;i<=n;i++){cin>>a[i];if(vis[a[i]]==0)vis[a[i]]=1,cout<<a[i]<<" ";}for(int i=1;i<=n;i++){if(vis[i]==0)cout<<i<<" ";}cout<<"\n";
}signed main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);cin>>t;while(t--)solve();return 0;
}

 E. Insane Problem

 思路：我们发现，若要y/x为k的次方，那我们不断将后面那个区间缩小，直到后面的右区间小于前面这个区间的左区间位置，不断计算两个区间的重复大小即可，但是要注意，缩小区间的时候，右端点要向下取整，左端点向上取整

#include<bits/stdc++.h>
using namespace std;
#define int long long
int t;
int k,a,b,c,d;
void solve()
{cin>>k>>a>>b>>c>>d;int flag=1;int ans=0;while(d>=a){int num=min(b,d)-max(a,c)+1;if(num<=0){num=0;}ans+=num;d/=k;c=(c+k-1)/k;}cout<<ans<<"\n";
}signed main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin>>t;while(t--)solve();return 0;
}

F. Easy Demon Problem

思路：我们自己手玩一下就发现了一个规律，整个M矩阵的美观值为列的累加和*行的累加和 

因此，我们可以去统计每个数是否出现过，出现过则标记为1，然后去判断是否出现过来输出YES或者NO，但是呢，不加剪枝的话时间复杂度就太高了，我们要将其中的大于N的部分全部去掉，这样时间复杂度为O（N根号N）

#include<bits/stdc++.h>
using namespace std;
#define int long long
int t;
int n,m,q;
const int N=200000;
int a[200005];
int b[200005];
int suma;
int sumb;
bool visa[400005];
bool visb[400005];
bool ans[400005];
void solve()
{cin>>n>>m>>q;suma=0,sumb=0;for(int i=1;i<=n;i++){cin>>a[i];suma+=a[i];}for(int i=1;i<=m;i++){cin>>b[i];sumb+=b[i];}int num=0;for(int i=1;i<=n;i++){num=suma-a[i];if(abs(num)<=N){visa[N+num]=true;}}for(int i=1;i<=m;i++){num=sumb-b[i];if(abs(num)<=N){visb[N+num]=true;}}for(int i=1;i<=N;i++){for(int j=1;j*i<=N;j++){ans[N+i*j]|=visa[N+i]&&visb[N+j];ans[N+i*j]|=visa[N-i]&&visb[N-j];ans[N-i*j]|=visa[N+i]&&visb[N-j];ans[N-i*j]|=visa[N-i]&&visb[N+j];}}while (q--){int x;cin >> x;x += N;if (ans[x])cout << "YES\n";elsecout << "NO\n";}
}signed main()
{solve();return 0;
}

 G1. Medium Demon Problem (easy version)

 思路：我们发现，只有强连通分量内的蜘蛛能够保持稳定，所以我们要输出的就是缩点后的最长的链然后+1就是最终答案

#include<bits/stdc++.h>  
using namespace std;  
#define int long long
int t;
int n;
vector<int> e[200005];
int dfn[200005];
int low[200005];
int len=0;
stack<int> s;
int vis[200005];
vector<int> scc[200005];
int cnt;
int dp[200005];
void ini()
{for(int i=1;i<=n;i++){e[i].clear();dfn[i]=low[i]=0;dp[i]=0;vis[i]=0;scc[i].clear();}len=0;cnt=0;
}
void tarjan(int v)
{dfn[v]=low[v]=++len;s.push(v);vis[v]=1;for(int u:e[v]){if(dfn[u]==0){tarjan(u);low[v]=min(low[v],low[u]);}else if(vis[u]==1){low[v]=min(low[v],dfn[u]);}}int u;if(low[v]==dfn[v]){cnt++;do{u=s.top();s.pop();vis[u]=0;scc[cnt].push_back(u);}while(u!=v);}
}
void solve() 
{cin>>n;vector<int> a(n+1);for(int i=1;i<=n;i++){cin>>a[i];e[i].push_back(a[i]);}for(int i=1;i<=n;i++){if(dfn[i]==0){tarjan(i);}}int ans=0;for(int i=1;i<=cnt;i++){if(scc[i].size()>1){for(int u:scc[i]){dp[u]=1;}ans=max(ans,1LL);}else{dp[scc[i][0]]=dp[a[scc[i][0]]]+1;ans=max(ans,dp[scc[i][0]]);}}cout<<ans+1<<"\n";;ini();
}
signed main() 
{  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);  cin >> t;  while (t--) {  solve();  }  return 0;  
}

G2. Medium Demon Problem (hard version)

因为每个蜘蛛可以保留多个，所以算的应当是除了强连通分量外的子树的最大值+1

#include<bits/stdc++.h>
using namespace std;
#define int long long
int t;
int n;
vector<int> e[200005];
int dfn[200005];
int low[200005];
int len;
stack<int> s;
int vis[200005];
vector<int> scc[200005];
int pos[200005];
int cnt;
int dp[200005];
void ini()
{for(int i=1;i<=n;i++){e[i].clear();dfn[i]=low[i]=0;dp[i]=0;vis[i]=0;pos[i]=0;scc[i].clear();}len=0;cnt=0;
}
void tarjan(int v)
{dfn[v]=low[v]=++len;s.push(v);vis[v]=1;for(int u:e[v]){if(dfn[u]==0){tarjan(u);low[v]=min(low[v],low[u]);}else if(vis[u]==1){low[v]=min(low[v],dfn[u]);}}int u;if(dfn[v]==low[v]){cnt++;do{u=s.top();s.pop();vis[u]=0;scc[cnt].push_back(u);pos[u]=cnt;}while(u!=v);}
}
void solve()
{cin>>n;vector<int> a(n+1);for(int i=1;i<=n;i++){cin>>a[i];e[i].push_back(a[i]);}for(int i=1;i<=n;i++){if(dfn[i]==0){tarjan(i);}}int ans=0;for(int i=1;i<=cnt;i++){dp[i]=1;if(scc[i].size()>1) dp[i]=0;}for(int i=cnt;i>=1;i--){if(scc[i].size()==1){int u=a[scc[i][0]];if (scc[pos[u]].size()==1) {dp[pos[u]]+=dp[i];} else {dp[pos[u]]=max(dp[pos[u]],dp[i]);}} else {ans=max(ans,dp[i]);}}cout<<ans+2<<"\n";ini();
}
signed main() 
{  ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);  cin>>t;  while(t--) {  solve();  }  return 0;  
}

 H. Hard Demon Problem

分析一下，求三个二维前缀和，就可以得到结果

#include <bits/stdc++.h>  
using namespace std;  
#define int long long
int n,q;
int a[2005][2005];  
int pre[2005][2005];  
int preX[2005][2005];  
int preY[2005][2005];  
void solve()   
{  cin>>n; cin >> q;  for (int i = 1; i <= n; i++) {  for (int j = 1; j <= n; j++) {  cin >> a[i][j];  pre[i][j] = a[i][j] + pre[i - 1][j] + pre[i][j - 1] - pre[i - 1][j - 1];  preX[i][j] = a[i][j] * i + preX[i - 1][j] + preX[i][j - 1] - preX[i - 1][j - 1];  preY[i][j] = a[i][j] * j + preY[i - 1][j] + preY[i][j - 1] - preY[i - 1][j - 1];  }  }  while (q--) {  int x1, y1, x2, y2;  cin >> x1 >> y1 >> x2 >> y2;  int sum = pre[x2][y2] - pre[x2][y1 - 1] - pre[x1 - 1][y2] + pre[x1 - 1][y1 - 1];  int sumX = preX[x2][y2] - preX[x2][y1 - 1] - preX[x1 - 1][y2] + preX[x1 - 1][y1 - 1];  int sumY = preY[x2][y2] - preY[x2][y1 - 1] - preY[x1 - 1][y2] + preY[x1 - 1][y1 - 1];  sumX -= sum * x1;  sumY -= sum * y1;  cout << sum + sumY + sumX * (y2 - y1 + 1) << " ";  }  cout<<"\n";
}  
signed main()   
{  ios::sync_with_stdio(false);  cin.tie(0);  int t, n;  cin >> t;  while (t--) {      solve();  }  return 0;  
}