有t组输入，每次给定一个长度为n的排列,里面只包含0~n-1，每个数恰好只出现一次，且顺序不定。我们需要找到两个下标i和j，使得的值最大化. 本题为交互题，每次询问的格式为”? a b c d”,最后会返回比较符号”<”或”=”或”>”,如果返回”<”，则说明，”=”和”>”同理。最终我们通过推理得到的答案用”! i j”的格式输出。
对于每次询问，我们询问出的答案只有大小关系而非具体的值，而且是或运算( | )的形式；由于每个数或上自己一定等于自己(x | x = x)，所以我们从第一数开始两两比较，每次记录下当前的最大值下标并更新，持续进行遍历询问，可以通过n-1次询问找到最大值也就是n-1的下标.不难想到，两数异或值最大，其中一个数必然可以是n-1，因为n-1一定包含了中最前面的1。所以现在的任务就是找到所有满足与n-1二进制值恰好“互补”的数的下标。
对于询问”? a b c d”，我们将a,c设为最大值下标，b设为当前最符合互补的数的下标，d设为i进行遍历，如果出现小于，则说明当前的数一定不互补，每次更新时b和d的值，例如当n=9时显然,假如，此时假如我们搜到的值为，那么，所以此时搜到的值一定是更加符合互补的值，将其更新到b；不难想到，最后一次出现”<”，说明当前和往后所有出现”=”的数，一定是互补的.例如当为最大值，那么最后一次出现”<”和往后的”=”一定是形如的二进制值！
#include<bits/stdc++.h> #define int long long #define endl "\n" using namespace std; int a[200010]; signed main(){ std::ios::sync_with_stdio(false);cin.tie(0); int T;cin>>T; while(T--){ int n;cin>>n; map<int,int>mp; for(int i=1;i<=n;i++) cin>>a[i],mp[a[i]]++; int tot=0; for(int i=1;i<=n;i++){ if(mp[a[i]]){ mp[a[i]]--; if(mp[(1LL<<31)-1-a[i]])mp[(1LL<<31)-1-a[i]]--; tot++; } } cout<<tot<<endl; } return 0; }
#include<bits/stdc++.h> #define int long long #define endl "\n" using namespace std; typedef pair<int,int>pii; int n,in[200010]; vector<int>e[200010]; bool toposort(){ //拓扑排序判环 queue<int>q; int tot=0; for(int i=1;i<=n;i++) if(!in[i])q.push(i),tot++; while(!q.empty()){ int temp=q.front(); q.pop(); for(auto it:e[temp]){ in[it]--; if(!in[it])q.push(it),tot++; } } if(tot==n)return 1; else return 0; } signed main(){ std::ios::sync_with_stdio(false);cin.tie(0); int T;T=1; cin>>T; while(T--){ int k;cin>>n>>k; set<pii>st; for(int i=1;i<=k;i++){ int y; for(int j=1;j<=n;j++){ //建边 int x;cin>>x; if(j==1)continue; if(j>2){ int num1=st.size(); st.insert({y,x}); int num2=st.size(); if(num1!=num2) //防止重复建边 e[y].push_back(x),in[x]++; } y=x; } } if(toposort())cout<<"YES"<<endl; else cout<<"NO"<<endl; //最后每次都记得清空数组和容器 for(int i=1;i<=n;i++)in[i]=0,e[i].clear(); } return 0; }
G. Destroying Bridges
签到题，随手画个图可知，当k小于n-1时，可访问所有岛屿，否则只能访问一个.
Code:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
#include <bits/stdc++.h> #define int long long #define endl '\n' using namespace std; signed main(){ std::ios::sync_with_stdio(false);cin.tie(0); int T;cin >> T; while (T--){ int n, k; cin >> n >> k; if (k < n - 1) cout << n << endl; else cout << "1" << endl; } return 0; }
H. Long Inversions(暴力+树状数组)
官方评分：*1700
个人评分：*1500
前置知识：树状数组
题意
给出长度为 的二进制字符串 。二进制字符串是仅由字符“1”和“0”组成的字符串。选择一个整数 ( )，然后多次应用以下操作：选择字符串中的 k 个连续字符并将它们反转，即将所有“0”替换为“1”，反之亦然。使用任意次操作，使字符串中的所有字符等于“1”。求出可以使字符串中的所有字符等于“1”的k的最大值。
#include<bits/stdc++.h> #define int long long #define endl '\n' #define INF 1e15 using namespace std; int n,a[5010],b[5010]; char s[5010]; int diff[5010]; signed main(){ std::ios::sync_with_stdio(false);cin.tie(0); int T;cin>>T; //树状数组实现“区间修改，单点查询”的功能 auto add1 = [&](int x, int k) -> void{ for (int i = x; i <= n;i+=i&(-i)) diff[i] += k; }; auto add2 = [&](int l, int r, int x) -> void{ add1(l, x), add1(r + 1, -x); }; auto query = [&](int x) -> int{ int res = 0; for (int i = x; i;i-=i&(-i)) res += diff[i]; return res; }; auto check = [&](int k) -> bool{ for (int i = 1; i <= n;i++) b[i] = a[i]; for (int i = 1; i <= n; i++) { int cnt = query(i) % 2; if (cnt) //操作次数为奇数时 b[i] ^= 1; if (i + k - 1 <= n){ if (b[i] == 0) add2(i, i + k - 1, 1); } else if (b[i] == 0) return 0; } return 1; }; while(T--){ cin >> n >> s + 1; int ans; for (int i = 1; i <= n; i++) a[i] = s[i] - '0'; for (int i = 1; i <= n; i++){ if (check(i)) ans = i; //记得每次操作过后要清除差分数组 for (int i = 1; i <= n;i++) diff[i] = 0; } cout << ans << endl; } return 0; }
#include <bits/stdc++.h> #define int long long #define endl '\n' using namespace std; signed main(){ std::ios::sync_with_stdio(false);cin.tie(0); T = 1;cin >> T; while (T--){ int n, cnt; cin >> n; for (int i = 0; i < 30; i++){ if (n >= (1 << i) && n < (1 << (i + 1))){ cnt = i; break; } } cout << (1 << cnt) << endl; } return 0; }
#include <bits/stdc++.h> #define int long long #define endl "\n" using namespace std; int t, n, a[100010], suf[100010]; signed main(){ std::ios::sync_with_stdio(false); cin >> t; while (t--) { cin >> n; for (int i = 1; i <= n; i++) cin >> a[i]; int ans = 0; for (int i = n; i >= 1; i--){ suf[i] = suf[i + 1] + a[i]; if (suf[i] > 0 || i == 1) //i=1必须分段，否则包含1的最前面一段可能直接舍弃了 ans += suf[i]; } cout << ans << endl; for (int i = 1; i <= n; i++) suf[i] = 0; } return 0; }
#include <bits/stdc++.h> #define int long long #define endl "\n" using namespace std; int t, n, k, maxn, a[200010], s[200010], h[200010], len[200010]; signed main(){ std::ios::sync_with_stdio(false);cin.tie(0); cin >> t; auto check=[&](int x) -> bool{ //二分判断的bool函数 for (int i = 1; i <= n + 1 - x; i++) if (s[i + x - 1] - s[i - 1] <= k && len[i + x - 1] - len[i] == x - 1) return 1; return 0; }; while (t--){ cin >> n >> k; bool flag = 0; for (int i = 1; i <= n; i++){ cin >> a[i], s[i] = a[i] + s[i - 1]; if (a[i] <= k) flag = 1; } for (int i = 1; i <= n; i++){ cin >> h[i]; if (i == 1) continue; else if (h[i - 1] % h[i] == 0) len[i] = len[i - 1] + 1; else len[i] = len[i - 1]; } if (!flag){ //当所有数的果实数均超过k,那么直接特判最大长度为0 cout << 0 << endl; continue; } int l = 1, r = 1e6, ans; while (l <= r){ int mid = (l + r) >> 1; if (check(mid)) l = mid + 1, ans = mid; else r = mid - 1; } cout << ans << endl; } return 0; }
微信
支付宝