Codeforces Round 888 (Div. 3)
A. Escalator Conversations
思路：暴力枚举
我们可以发现要让他们能相同高度首先你们之间的差值必须是k的倍数并且这个倍数必须小于m并且不能存在相同高度
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i,a,n) for(int i=a;i<=n;i++)
#define per(i,a,n) for(int i=n;i>=a;i--)
#define pb push_back
#define SZ(v) ((int)v.size())
#define fs first
#define sc second
const int N=2e6+10,M=2e5;
typedef double db;
typedef pair<int,int>pii;
int n,m,k,Q,cnt,t,H;
vector<int>del;
int a[200010],b[200010];
int prime[N];
bool st[N];
map<int,int>mp;
void solve(){std::cin>>n>>m>>k>>H;int res=0;rep(i,1,n){int x;std::cin>>x;int y=abs(x-H);if(y%k==0&&y/k<=m-1&&y)res++;}std::cout<<res<<endl;}
signed main(){std::cin>>t;while(t--)solve();
}
B. Parity Sort
思路：贪心排序
我们可以发现直接对奇数数值和偶数数值进行排序,然后判断是不是非递减序列即可
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i,a,n) for(int i=a;i<=n;i++)
#define per(i,a,n) for(int i=n;i>=a;i--)
#define pb push_back
#define SZ(v) ((int)v.size())
#define fs first
#define sc second
const int N=2e6+10,M=2e5;
typedef double db;
typedef pair<int,int>pii;
int n,m,k,Q,cnt,t,H;
vector<int>del;
int a[200010],b[200010],c[N];
int prime[N];
bool st[N];
map<int,int>mp;
void solve(){std::cin>>n;rep(i,1,n)std::cin>>a[i];int l=0,r=0;rep(i,1,n){if(a[i]&1)b[l++]=a[i];else c[r++]=a[i];}std::sort(b,b+l);std::sort(c,c+r);//rep(i,1,l)cout<<b[i]<<endl;int l1=0,r1=0;rep(i,1,n){if(a[i]&1)a[i]=b[l1++];else a[i]=c[r1++];}int f=1;rep(i,1,n-1){if(a[i]>a[i+1]){f=0;break;}}if(f)std::cout<<"YES"<<endl;else std::cout<<"NO"<<endl;
}
signed main(){std::cin>>t;while(t--)solve();
}
C. Tiles Comeback
思路：贪心
只要有k个元素和第一个元素颜色相同，并且有k个元素和最后一个元素颜色相同 ，并且选择这两种颜色的区间不相交，答案即为YES。特别的是，第一个元素和最后一个元素颜色相同，此时只需要k个颜色即可
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i,a,n) for(int i=a;i<=n;i++)
#define per(i,a,n) for(int i=n;i>=a;i--)
#define pb push_back
#define SZ(v) ((int)v.size())
#define fs first
#define sc second
const int N=2e6+10,M=2e5;
typedef double db;
typedef pair<int,int>pii;
int n,m,k,Q,cnt,t,H;
vector<int>del;
int a[200010],b[200010],c[N];
int prime[N];
bool st[N];void solve() {pii l,r;int n,k;cin>>n>>k;for(int i=1; i<=n; i++) {cin>>a[i];if(a[i]==a[1]&&l.second!=k)l.first=i,l.second++;}for(int i=n; i>=1; i--) {if(a[i]==a[n]&&r.second!=k)r.first=i,r.second++;}if(l.second!=k||r.second!=k) {std::cout<<"NO\n";return;}if(a[1]==a[n]) std::cout<<"YES\n";else {if(l.first<r.first)std::cout<<"YES\n";else std::cout<<"NO\n";}
}
signed main(){std::cin>>t;while(t--)solve();
}
D. Prefix Permutation Sums
思路：模拟
我们可以发现，如果一个前缀和去掉一个数会存在三种情况：
① 删除第一个数
② 删除中间的数
③ 删除结尾的数
我们可以找到前缀和的差值，特别的把第一位加入进去并标记，然后记录在1~n中不存在的数的和s以及个数x，这里如果满足一下三种情况即为yes：
① 如果s>n并且在差值里面只出现一次并且x ==2
② 如果s<=n并且在差值里面只出现两次并且x ==2
③ 如果x ==1
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i,a,n) for(int i=a;i<=n;i++)
#define per(i,a,n) for(int i=n;i>=a;i--)
#define pb push_back
#define SZ(v) ((int)v.size())
#define fs first
#define sc second
const int N=2e6+10,M=2e5;
typedef double db;
typedef pair<int,int>pii;
int n,m,k,Q,cnt,t,H;
vector<int>del;
int a[200010],b[200010],c[N];
int prime[N];
bool st[N];void solve(){std::cin>>n;rep(i,1,n-1)cin>>a[i];map<int,int>mp;mp[a[1]]++;rep(i,2,n-1){mp[a[i]-a[i-1]]++;}int x=0,y=0,s=0;rep(i,1,n){//cout<<mp[i]<<endl;if(mp[i]==0){s+=i;x++;}}//cout<<x<<" "<<y<<endl;if((mp[s]==1&&x==2&&s>n)||(mp[s]==2&&x==2&&s<=n)||x==1)std::cout<<"YES\n";else std::cout<<"NO\n";
}
signed main(){std::cin>>t;while(t--)solve();
}
E. Nastya and Potions
思路：dfs+记忆化
典型的有向无环图的记忆化搜索，有人说dp其实都一样，我们通过记忆化搜索（dfs） 的方法来确定他每一种原料的最小花销，这样就能得到通过合成路线相加获得该药剂的最小花销。之后我们将这个价格和市场价格做比对，保留最小值即可，并记得标记已经得到的答案，已便用它来更新答案
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i,a,n) for(int i=a;i<=n;i++)
#define per(i,a,n) for(int i=n;i>=a;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 N=2e6+10;
typedef double db;
typedef pair<int,int>pii;
int n,m,k,Q,cnt,t,H;
vector<int>g[N];
int w[N];
bool st[N];
void dfs(int u){int res=0;if(g[u].size()==0){st[u]=1;return ;}for(auto ed:g[u]){if(!st[ed]){dfs(ed);res+=w[ed];}else{res+=w[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::cin>>t;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 pair<int, 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();
}
