网站自适应屏幕,做电商的女人不干净,免费咨询心理问题,做网站商丘A. Easy Problem 思路#xff1a;经过看了一眼#xff0c;我们发现#xff0c;ab的和一定是n#xff0c;且两个都是正整数#xff0c;
所以a的范围就是从1~n-1
所以输出n-1即可
#includebits/stdc.h
using namespace std;
#define int long long
int t;
int n…
A. Easy Problem 思路经过看了一眼我们发现ab的和一定是n且两个都是正整数
所以a的范围就是从1~n-1
所以输出n-1即可
#includebits/stdc.h
using namespace std;
#define int long long
int t;
int n,k;
int a,b;
string s;
void solve()
{cinn;coutn-1\n;
}signed main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);cint;while(t--)solve();return 0;
}
B. Normal Problem 思路稍加思索一下就发现其实从里面看的话就是将字符串翻转之后将p变成q将q变成p
#includebits/stdc.h
using namespace std;
#define int long long
int t;
int n,k;
int a,b;
string s;
void solve()
{cins;for(int i0;is.size();i){if(s[i]p){s[i]q;}else if(s[i]q){s[i]p;}}reverse(s.begin(),s.end());couts\n;
}signed main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);cint;while(t--)solve();return 0;
} C. Hard Problem 思路第一排尽量都坐满a,第二排尽量坐满b然后空的用c补全直到座位为0或者c没有了
#includebits/stdc.h
using namespace std;
#define int long long
int t;
int n,k;
int a,b,c;
string s;
void solve()
{cinnabc;int ans0;coutmin(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);cint;while(t--)solve();return 0;
} D. Harder Problem 思路我们有n个位置放数那我们就按照123...n这种情况放数这样每个数只出现一次都可以作为模数但是要注意数出现的顺序所以我们出现一个新的就输出当前这个数然后遍历1~n看哪个数还没出现过没出现则输出
#includebits/stdc.h
using namespace std;
#define int long long
int t;
int n,k;
int a[200005];
void solve()
{cinn;int vis[200005];memset(vis,0,sizeof(vis));for(int i1;in;i){cina[i];if(vis[a[i]]0)vis[a[i]]1,couta[i] ;}for(int i1;in;i){if(vis[i]0)couti ;}cout\n;
}signed main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);cint;while(t--)solve();return 0;
} E. Insane Problem 思路我们发现若要y/x为k的次方那我们不断将后面那个区间缩小直到后面的右区间小于前面这个区间的左区间位置不断计算两个区间的重复大小即可但是要注意缩小区间的时候右端点要向下取整左端点向上取整
#includebits/stdc.h
using namespace std;
#define int long long
int t;
int k,a,b,c,d;
void solve()
{cinkabcd;int flag1;int ans0;while(da){int nummin(b,d)-max(a,c)1;if(num0){num0;}ansnum;d/k;c(ck-1)/k;}coutans\n;
}signed main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cint;while(t--)solve();return 0;
}
F. Easy Demon Problem 思路我们自己手玩一下就发现了一个规律整个M矩阵的美观值为列的累加和*行的累加和
因此我们可以去统计每个数是否出现过出现过则标记为1然后去判断是否出现过来输出YES或者NO但是呢不加剪枝的话时间复杂度就太高了我们要将其中的大于N的部分全部去掉这样时间复杂度为ON根号N
#includebits/stdc.h
using namespace std;
#define int long long
int t;
int n,m,q;
const int N200000;
int a[200005];
int b[200005];
int suma;
int sumb;
bool visa[400005];
bool visb[400005];
bool ans[400005];
void solve()
{cinnmq;suma0,sumb0;for(int i1;in;i){cina[i];sumaa[i];}for(int i1;im;i){cinb[i];sumbb[i];}int num0;for(int i1;in;i){numsuma-a[i];if(abs(num)N){visa[Nnum]true;}}for(int i1;im;i){numsumb-b[i];if(abs(num)N){visb[Nnum]true;}}for(int i1;iN;i){for(int j1;j*iN;j){ans[Ni*j]|visa[Ni]visb[Nj];ans[Ni*j]|visa[N-i]visb[N-j];ans[N-i*j]|visa[Ni]visb[N-j];ans[N-i*j]|visa[N-i]visb[Nj];}}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就是最终答案
#includebits/stdc.h
using namespace std;
#define int long long
int t;
int n;
vectorint e[200005];
int dfn[200005];
int low[200005];
int len0;
stackint s;
int vis[200005];
vectorint scc[200005];
int cnt;
int dp[200005];
void ini()
{for(int i1;in;i){e[i].clear();dfn[i]low[i]0;dp[i]0;vis[i]0;scc[i].clear();}len0;cnt0;
}
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{us.top();s.pop();vis[u]0;scc[cnt].push_back(u);}while(u!v);}
}
void solve()
{cinn;vectorint a(n1);for(int i1;in;i){cina[i];e[i].push_back(a[i]);}for(int i1;in;i){if(dfn[i]0){tarjan(i);}}int ans0;for(int i1;icnt;i){if(scc[i].size()1){for(int u:scc[i]){dp[u]1;}ansmax(ans,1LL);}else{dp[scc[i][0]]dp[a[scc[i][0]]]1;ansmax(ans,dp[scc[i][0]]);}}coutans1\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
#includebits/stdc.h
using namespace std;
#define int long long
int t;
int n;
vectorint e[200005];
int dfn[200005];
int low[200005];
int len;
stackint s;
int vis[200005];
vectorint scc[200005];
int pos[200005];
int cnt;
int dp[200005];
void ini()
{for(int i1;in;i){e[i].clear();dfn[i]low[i]0;dp[i]0;vis[i]0;pos[i]0;scc[i].clear();}len0;cnt0;
}
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{us.top();s.pop();vis[u]0;scc[cnt].push_back(u);pos[u]cnt;}while(u!v);}
}
void solve()
{cinn;vectorint a(n1);for(int i1;in;i){cina[i];e[i].push_back(a[i]);}for(int i1;in;i){if(dfn[i]0){tarjan(i);}}int ans0;for(int i1;icnt;i){dp[i]1;if(scc[i].size()1) dp[i]0;}for(int icnt;i1;i--){if(scc[i].size()1){int ua[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 {ansmax(ans,dp[i]);}}coutans2\n;ini();
}
signed main()
{ ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); cint; 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()
{ cinn; 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;
}
