做网站时怎样申请域名,建设银行网站用户名,金华建设学校继续教育网站,建筑八大员培训机构Codeforces Round 888 (Div. 3)
A. Escalator Conversations
思路#xff1a;暴力枚举 我们可以发现要让他们能相同高度首先你们之间的差值必须是k的倍数并且这个倍数必须小于m并且不能存在相同高度
#includebits/stdc.h
using namespace std;
#define int long lo…Codeforces Round 888 (Div. 3)
A. Escalator Conversations
思路暴力枚举 我们可以发现要让他们能相同高度首先你们之间的差值必须是k的倍数并且这个倍数必须小于m并且不能存在相同高度
#includebits/stdc.h
using namespace std;
#define int long long
#define rep(i,a,n) for(int ia;in;i)
#define per(i,a,n) for(int in;ia;i--)
#define pb push_back
#define SZ(v) ((int)v.size())
#define fs first
#define sc second
const int N2e610,M2e5;
typedef double db;
typedef pairint,intpii;
int n,m,k,Q,cnt,t,H;
vectorintdel;
int a[200010],b[200010];
int prime[N];
bool st[N];
mapint,intmp;
void solve(){std::cinnmkH;int res0;rep(i,1,n){int x;std::cinx;int yabs(x-H);if(y%k0y/km-1y)res;}std::coutresendl;}
signed main(){std::cint;while(t--)solve();
}B. Parity Sort
思路贪心排序 我们可以发现直接对奇数数值和偶数数值进行排序,然后判断是不是非递减序列即可
#includebits/stdc.h
using namespace std;
#define int long long
#define rep(i,a,n) for(int ia;in;i)
#define per(i,a,n) for(int in;ia;i--)
#define pb push_back
#define SZ(v) ((int)v.size())
#define fs first
#define sc second
const int N2e610,M2e5;
typedef double db;
typedef pairint,intpii;
int n,m,k,Q,cnt,t,H;
vectorintdel;
int a[200010],b[200010],c[N];
int prime[N];
bool st[N];
mapint,intmp;
void solve(){std::cinn;rep(i,1,n)std::cina[i];int l0,r0;rep(i,1,n){if(a[i]1)b[l]a[i];else c[r]a[i];}std::sort(b,bl);std::sort(c,cr);//rep(i,1,l)coutb[i]endl;int l10,r10;rep(i,1,n){if(a[i]1)a[i]b[l1];else a[i]c[r1];}int f1;rep(i,1,n-1){if(a[i]a[i1]){f0;break;}}if(f)std::coutYESendl;else std::coutNOendl;
}
signed main(){std::cint;while(t--)solve();
}C. Tiles Comeback
思路贪心 只要有k个元素和第一个元素颜色相同并且有k个元素和最后一个元素颜色相同 并且选择这两种颜色的区间不相交答案即为YES。特别的是第一个元素和最后一个元素颜色相同此时只需要k个颜色即可
#includebits/stdc.h
using namespace std;
#define int long long
#define rep(i,a,n) for(int ia;in;i)
#define per(i,a,n) for(int in;ia;i--)
#define pb push_back
#define SZ(v) ((int)v.size())
#define fs first
#define sc second
const int N2e610,M2e5;
typedef double db;
typedef pairint,intpii;
int n,m,k,Q,cnt,t,H;
vectorintdel;
int a[200010],b[200010],c[N];
int prime[N];
bool st[N];void solve() {pii l,r;int n,k;cinnk;for(int i1; in; i) {cina[i];if(a[i]a[1]l.second!k)l.firsti,l.second;}for(int in; i1; i--) {if(a[i]a[n]r.second!k)r.firsti,r.second;}if(l.second!k||r.second!k) {std::coutNO\n;return;}if(a[1]a[n]) std::coutYES\n;else {if(l.firstr.first)std::coutYES\n;else std::coutNO\n;}
}
signed main(){std::cint;while(t--)solve();
}D. Prefix Permutation Sums
思路模拟 我们可以发现如果一个前缀和去掉一个数会存在三种情况 ① 删除第一个数 ② 删除中间的数 ③ 删除结尾的数 我们可以找到前缀和的差值特别的把第一位加入进去并标记然后记录在1~n中不存在的数的和s以及个数x这里如果满足一下三种情况即为yes ① 如果sn并且在差值里面只出现一次并且x 2 ② 如果sn并且在差值里面只出现两次并且x 2 ③ 如果x 1
#includebits/stdc.h
using namespace std;
#define int long long
#define rep(i,a,n) for(int ia;in;i)
#define per(i,a,n) for(int in;ia;i--)
#define pb push_back
#define SZ(v) ((int)v.size())
#define fs first
#define sc second
const int N2e610,M2e5;
typedef double db;
typedef pairint,intpii;
int n,m,k,Q,cnt,t,H;
vectorintdel;
int a[200010],b[200010],c[N];
int prime[N];
bool st[N];void solve(){std::cinn;rep(i,1,n-1)cina[i];mapint,intmp;mp[a[1]];rep(i,2,n-1){mp[a[i]-a[i-1]];}int x0,y0,s0;rep(i,1,n){//coutmp[i]endl;if(mp[i]0){si;x;}}//coutx yendl;if((mp[s]1x2sn)||(mp[s]2x2sn)||x1)std::coutYES\n;else std::coutNO\n;
}
signed main(){std::cint;while(t--)solve();
}E. Nastya and Potions
思路dfs记忆化 典型的有向无环图的记忆化搜索有人说dp其实都一样我们通过记忆化搜索dfs 的方法来确定他每一种原料的最小花销这样就能得到通过合成路线相加获得该药剂的最小花销。之后我们将这个价格和市场价格做比对保留最小值即可并记得标记已经得到的答案已便用它来更新答案
#includebits/stdc.h
using namespace std;
#define int long long
#define rep(i,a,n) for(int ia;in;i)
#define per(i,a,n) for(int in;ia;i--)
#define pb push_back
#define SZ(v) ((int)v.size())
#define fs first
#define sc second
#define DFX ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
const int N2e610;
typedef double db;
typedef pairint,intpii;
int n,m,k,Q,cnt,t,H;
vectorintg[N];
int w[N];
bool st[N];
void dfs(int u){int res0;if(g[u].size()0){st[u]1;return ;}for(auto ed:g[u]){if(!st[ed]){dfs(ed);resw[ed];}else{resw[ed];}}st[u]1;w[u]min(w[u],res);
}void solve()
{memset(st, false, sizeof st); // 一定要初始化cin n k;for (int i 1; i n; i) // 一定要初始化把图清空g[i].clear();for (int i 1; i n; i)cin w[i];for (int i 1; i k; i){int x;cin x;w[x] 0; // 如果拥有无限的这种药水那就价值为零st[x] true; // 并且标记这种药水不用再dfs了}for (int i 1; i n; i){int x;cin x; // 读入每种药水的制作要求for (int j 1; j x; j){int v;cin v;g[i].push_back(v);}}for (int i 1; i n; i){if (!st[i]) // 如果没有计算过就dfs在输出dfs(i);cout w[i] ; // 否则直接输出}cout endl;
}signed main(){DFX;std::cint;while(t--)solve();
}F. Lisa and the Martians
思路 copy下别人的思路
#include bits/stdc.h
using namespace std;
#define pi acos(-1)
#define xx first
#define yy second
#define endl \n
#define int long long
#define pb push_back
typedef pairint, int PII;
#define max(a, b) (((a) (b)) ? (a) : (b))
#define min(a, b) (((a) (b)) ? (a) : (b))
#define Ysanqian ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
const int N 1e6 10, M 1010, inf 0x3f3f3f3f, mod 998244353;
int n, k;
PII a[N];
bool cmp(PII a, PII b)
{return a.xx b.xx;
}
void solve()
{int minn 2e9;cin n k;for (int i 1; i n; i){cin a[i].xx;a[i].yy i;}sort(a 1, a 1 n, cmp);int idx 2;for (int i 2; i n; i){if (minn (a[i].xx ^ a[i - 1].xx)){minn (a[i].xx ^ a[i - 1].xx);idx i;}}int m ((1 k) - 1) ^ a[idx].xx;cout a[idx].yy a[idx - 1].yy m endl;
}
signed main()
{Ysanqian;int T;// T 1;cin T;while (T--)solve();
}
