末尾是偶数0
第一位是偶数1
如果有偶数是2
否则是-1
#includeusing namespace std; std::mt19937 rng(std::random_device{}()); typedef long double ld; typedef long long ll; typedef unsigned long long ull; typedef const int& cint; typedef const ll& cll; typedef pair pii; typedef pair pil; #define ls (loc<<1) #define rs ((loc<<1)|1) const int mod1 = 1e9+7; const int mod2 = 998244353; const int inf_int = 0x7fffffff; const int hf_int = 0x3f3f3f3f; const ll inf_ll = 0x7fffffffffffffff; const double ept = 1e-9; int t; char s[100100]; int main() { //freopen("1.in", "r", stdin); //cout.flags(ios::fixed); cout.precision(8); ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int T_=1; std::cin >> T_; for(int _T=1; _T<=T_; _T++) { cin >> s; int le = strlen(s); if(!((s[le-1]-'0')%2)) cout << 0 << endl; else if(!((s[0]-'0')%2)) cout << 1 << endl; else { bool flag = 0; for(int i=0; i B 假定 a < b a
如果 a ∗ 3 < b a*3
否则全部都能取完
#includeCusing namespace std; std::mt19937 rng(std::random_device{}()); typedef long double ld; typedef long long ll; typedef unsigned long long ull; typedef const int& cint; typedef const ll& cll; typedef pair pii; typedef pair pil; #define ls (loc<<1) #define rs ((loc<<1)|1) const int mod1 = 1e9+7; const int mod2 = 998244353; const int inf_int = 0x7fffffff; const int hf_int = 0x3f3f3f3f; const ll inf_ll = 0x7fffffffffffffff; const double ept = 1e-9; ll a, b; int main() { //freopen("1.in", "r", stdin); //cout.flags(ios::fixed); cout.precision(8); ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int T_=1; std::cin >> T_; for(int _T=1; _T<=T_; _T++) { cin >> a >> b; if(a > b) swap(a, b); if(a*3 < b) cout << a << endl; else cout << (a+b)/4 << endl; } return 0; } 如果最大值在左边或右边一定成立,否则一定不成立
构造答案考虑将最大值放在边上,其余值倒序一下
#includeDusing namespace std; std::mt19937 rng(std::random_device{}()); typedef long double ld; typedef long long ll; typedef unsigned long long ull; typedef const int& cint; typedef const ll& cll; typedef pair pii; typedef pair pil; #define ls (loc<<1) #define rs ((loc<<1)|1) const int mod1 = 1e9+7; const int mod2 = 998244353; const int inf_int = 0x7fffffff; const int hf_int = 0x3f3f3f3f; const ll inf_ll = 0x7fffffffffffffff; const double ept = 1e-9; int n; int a[200200]; int to[200200]; int main() { //freopen("1.in", "r", stdin); //cout.flags(ios::fixed); cout.precision(8); ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int T_=1; std::cin >> T_; for(int _T=1; _T<=T_; _T++) { cin >> n; for(int i=1; i<=n; i++) cin >> a[i]; for(int i=1; i<=n; i++) to[a[i]] = i; vector ans; if(to[n] != 1 && to[n] != n) cout << -1; else { if(to[n] == n) { for(int i=n-1; i>=1; i--) ans.push_back(a[i]); ans.push_back(n); } else { ans.push_back(n); for(int i=n; i>1; i--) ans.push_back(a[i]); } } for(int i: ans) cout << i << ' '; cout << endl; } return 0; } 按顺序枚举给定排列,如果轮到一个点时他的父亲还没有被访问过,那么不成立,否则成立
构造答案考虑到根距离等于上一个枚举的点到根的距离+1,然后计算路径长度
#includeEusing namespace std; std::mt19937 rng(std::random_device{}()); typedef long double ld; typedef long long ll; typedef unsigned long long ull; typedef const int& cint; typedef const ll& cll; typedef pair pii; typedef pair pil; #define ls (loc<<1) #define rs ((loc<<1)|1) const int mod1 = 1e9+7; const int mod2 = 998244353; const int inf_int = 0x7fffffff; const int hf_int = 0x3f3f3f3f; const ll inf_ll = 0x7fffffffffffffff; const double ept = 1e-9; int n; int b[200200], p[200200]; int dis[200200]; int ans[200200]; int main() { //freopen("1.in", "r", stdin); //cout.flags(ios::fixed); cout.precision(8); ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int T_=1; std::cin >> T_; for(int _T=1; _T<=T_; _T++) { cin >> n; for(int i=1; i<=n; i++) cin >> b[i]; for(int i=1; i<=n; i++) cin >> p[i]; bool flag = 0; for(int i=1; i<=n; i++) dis[i] = -1; if(b[p[1]] != p[1]) flag = 1; else { dis[p[1]] = 0; ans[p[1]] = 0; } for(int i=2; i<=n; i++) { if(flag) break; int fa = b[p[i]]; if(dis[fa] < 0) flag = 1; else { dis[p[i]] = dis[p[i-1]] + 1; ans[p[i]] = dis[p[i]] - dis[fa]; } } if(flag) cout << -1 << endl; else { for(int i=1; i<=n; i++) cout << ans[i] << ' '; cout << endl; } } return 0; } e1:因为是树,朋友的最优行动肯定是贪心往上走,记录每一个点被朋友所占据的时间数,然后从1开始dfs,如果到某个节点的时间大于等于朋友占据的时间,那么肯定走不到,返回,能到一个叶子说明自己能赢
e2:在e1的基础上,如果不能赢的话,记录dfs中碰到的朋友数,就是答案
#includeFusing namespace std; std::mt19937 rng(std::random_device{}()); typedef long double ld; typedef long long ll; typedef unsigned long long ull; typedef const int& cint; typedef const ll& cll; typedef pair pii; typedef pair pil; #define ls (loc<<1) #define rs ((loc<<1)|1) const int mod1 = 1e9+7; const int mod2 = 998244353; const int inf_int = 0x7fffffff; const int hf_int = 0x3f3f3f3f; const ll inf_ll = 0x7fffffffffffffff; const double ept = 1e-9; int n, k; bool pe[200200]; vector to[200200]; int tim[200200]; int ans; void dfs(cint u, cint fa) { for(int v: to[u]) if(v != fa) dfs(v, u); if(pe[u]) tim[u] = 0; else tim[u] = hf_int; for(int v: to[u]) if(v != fa) tim[u] = min(tim[u], tim[v]+1); // cout << u << ' ' << fa << ' ' << tim[u] << endl; } bool check(cint u, cint fa, cint step) { if(tim[u] <= step) { ++ans; return 0; } if(to[u].size() == 1 && u != 1) return 1; bool flag = 0; for(int v: to[u]) if(v != fa) flag |= check(v, u, step+1); return flag; } int main() { // freopen("1.in", "r", stdin); //cout.flags(ios::fixed); cout.precision(8); ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int T_=1; std::cin >> T_; for(int _T=1; _T<=T_; _T++) { cin >> n >> k; ans = 0; for(int i=1; i<=n; i++) pe[i] = 0; for(int i=1; i<=k; i++) { int tmp; cin >> tmp; pe[tmp] = 1; } int u, v; for(int i=1; i<=n; i++) to[i].clear(); for(int i=1; i > u >> v; to[u].push_back(v); to[v].push_back(u); } dfs(1, 1); if(check(1, 1, 0)) cout << -1 << endl; else cout << ans << endl; } return 0; } 可以二分+st表
也可以双指针,下面说双指针
假设从第一个人服务,确定了一个r,那么如果要让r更大,就需要前面扣得钱更少,这是一个递增的过程,所以在移动l的过程中不会有中间无解的情况出现
#includeGusing namespace std; std::mt19937 rng(std::random_device{}()); typedef long double ld; typedef long long ll; typedef unsigned long long ull; typedef const int& cint; typedef const ll& cll; typedef pair pii; typedef pair pil; #define ls (loc<<1) #define rs ((loc<<1)|1) const int mod1 = 1e9+7; const int mod2 = 998244353; const int inf_int = 0x7fffffff; const int hf_int = 0x3f3f3f3f; const ll inf_ll = 0x7fffffffffffffff; const double ept = 1e-9; int n; ll s; ll a[200200]; int main() { // freopen("1.in", "r", stdin); //cout.flags(ios::fixed); cout.precision(8); ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int T_=1; std::cin >> T_; for(int _T=1; _T<=T_; _T++) { cin >> n >> s; for(int i=1; i<=n; i++) cin >> a[i]; for(int i=1; i<=n; i++) a[i] += a[i-1]; int r = 1, ans = -1, lst = -inf_int; int al, ar; for(int i=1; i<=n; i++) { if(r < i) { r = i; lst = -inf_int; } if(-a[i-1] >= lst && a[i]-a[i-1]+s >= 0) { while(r <= n && a[r]-a[i-1]+s >= 0) ++r; if(r-i+1 > ans) { ans = r-i+1; al = i; ar = r-1; } lst = -a[i-1]; } } if(ans <= 0) cout << -1 << endl; else cout << al << ' ' << ar << endl; } return 0; } 不会
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)