A
#include <bits/stdc++.h> #define PI acos(-1.0) #define mem(a,b) memset((a),b,sizeof(a)) #define TS printf("!!! ") #define pb push_back #define inf 1e9 //std::ios::sync_with_stdio(false); using namespace std; //priority_queue<int,vector<int>,greater<int>> que; get min const double eps = 1.0e-8; typedef pair<int, int> pairint; typedef long long ll; typedef unsigned long long ull; const int maxn = 4000003; const int maxm = 2000010; const int turn[4][2] = {{1, 0}, { -1, 0}, {0, 1}, {0, -1}}; //priority_queue<int, vector<int>, less<int>> que; //next_permutation int num[5005]; int main() { int n; cin >> n; for(int i=1; i<=n; i++) { cin >> num[i]; } int flag=0; for(int i=1; i<=n; i++) { int time=2; int aim=num[i]; while(time--) { aim=num[aim]; } if(aim==i) { cout<<"YES"<<endl; return 0; } } cout<<"NO"<<endl; return 0; }
B
#include <bits/stdc++.h> #define PI acos(-1.0) #define mem(a,b) memset((a),b,sizeof(a)) #define TS printf("!!! ") #define pb push_back #define inf 1e9 //std::ios::sync_with_stdio(false); using namespace std; //priority_queue<int,vector<int>,greater<int>> que; get min const double eps = 1.0e-10; const double EPS = 1.0e-4; typedef pair<int, int> pairint; typedef long long ll; typedef unsigned long long ull; //const int maxn = 3e5 + 10; const int turn[4][2] = {{1, 0}, { -1, 0}, {0, 1}, {0, -1}}; //priority_queue<int, vector<int>, less<int>> que; //next_permutation ll Mod = 1000000007; int main() { ll aim=0,anser; ll remain=1e18+1; ll n,k; cin >> n >> k; for(int i=1;i<=k;i++) { ll now; cin >> now; if((n-1LL*n/now*now)<remain) { aim=i; anser=n/now; remain=n-1LL*n/now*now; } } cout<<aim<<" "<<anser<<endl; return 0; }
C
不能用前缀和向后推来判断 应该要向前推
#include <bits/stdc++.h> #define PI acos(-1.0) #define mem(a,b) memset((a),b,sizeof(a)) #define TS printf("!!! ") #define pb push_back #define inf 1e9 //std::ios::sync_with_stdio(false); using namespace std; //priority_queue<int,vector<int>,greater<int>> que; get min const double eps = 1.0e-10; const double EPS = 1.0e-4; typedef pair<int, int> pairint; typedef long long ll; typedef unsigned long long ull; //const int maxn = 3e5 + 10; const int turn[4][2] = {{1, 0}, { -1, 0}, {0, 1}, {0, -1}}; //priority_queue<int, vector<int>, less<int>> que; //next_permutation ll Mod = 1000000007; ll num[200005]; ll pre[200005]; ll ans; ll now; int main() { int n; cin >> n; for (int i = 1; i <= n; i++) { scanf("%lld", num + i); num[i + n] = num[i]; } ll L, R; cin >> L >> R; for (int i = L; i < R; i++) { ans += num[i]; } now = ans; int aim = 1; for (int i = 2; i <= n; i++) { now = now - num[1 + n + R - i] + num[1 + n + L - i]; if (now > ans) { aim = i; ans = now; } } cout << aim << endl; return 0; }
D
转化题意为求联通块 可以并查集也可以直接DFS 答案为每个联通块内点数-1的和
#include <bits/stdc++.h> #define PI acos(-1.0) #define mem(a,b) memset((a),b,sizeof(a)) #define TS printf("!!! ") #define pb push_back #define inf 1e9 //std::ios::sync_with_stdio(false); using namespace std; //priority_queue<int,vector<int>,greater<int>> que; get min const double eps = 1.0e-10; const double EPS = 1.0e-4; typedef pair<int, int> pairint; typedef long long ll; typedef unsigned long long ull; //const int maxn = 3e5 + 10; const int turn[4][2] = {{1, 0}, { -1, 0}, {0, 1}, {0, -1}}; //priority_queue<int, vector<int>, less<int>> que; //next_permutation ll Mod = 1000000007; string a, b; int gra[30][30]; int visit[30]; int belong[30]; int block[30]; void dfs(int x, int aim) { visit[x] = 1; belong[x] = aim; for (int i = 0; i <= 25; i++) { if (gra[x][i] && !visit[i]) { block[aim]++; dfs(i, aim); } } } int main() { for (int i = 0; i <= 25; i++) { belong[i] = 30; } for (int i = 0; i <= 25; i++) { block[i] = visit[i] = 1; } int n; cin >> n; cin >> a >> b; for (int i = 0; i < n; i++) { if (a[i] != b[i]) { visit[a[i] - 'a'] = visit[b[i] - 'a'] = 0; gra[a[i] - 'a'][b[i] - 'a'] = gra[b[i] - 'a'][a[i] - 'a'] = 1; } } for (int i = 0; i <= 25; i++) { if (visit[i]) { continue; } dfs(i, i); } int ans = 0; for (int i = 0; i <= 25; i++) { if (block[i] > 1) { ans += block[i] - 1; } } cout << ans << endl; for (int i = 0; i <= 25; i++) { if (belong[i] != 30 && i != belong[i]) { cout << (char)('a' + i) << " " << (char)('a' + belong[i]) << endl; } } return 0; }
E
裸的一个三分 分析题意可以得到 答案为 ans=maxn-(maxn+pre[k])/(k+1) 为凸函数
也可以记录前一个query的答案然后向后推进
因为随着最大值越来越大maxn-(maxn+pre[k])/(k+1)的值会越来越大 而你要求加进去的前缀里的数只要小于(maxn+pre[k])/(k+1)这个平均值就可以了
#include <bits/stdc++.h> #define PI acos(-1.0) #define mem(a,b) memset((a),b,sizeof(a)) #define TS printf("!!! ") #define pb push_back #define inf 1e9 //std::ios::sync_with_stdio(false); using namespace std; //priority_queue<int,vector<int>,greater<int>> que; get min const double eps = 1.0e-10; const double EPS = 1.0e-4; typedef pair<int, int> pairint; typedef long long ll; typedef unsigned long long ull; //const int maxn = 3e5 + 10; const int turn[4][2] = {{1, 0}, { -1, 0}, {0, 1}, {0, -1}}; //priority_queue<int, vector<int>, less<int>> que; //next_permutation ll Mod = 1000000007; ll num[500005]; ll pre[500005]; int pop; int l, r; double f(int x) { return ((double)(num[pop]) - (((double)(num[pop]) + (double)(pre[x])) / (double)(x + 1))); } double SF() { while (l < r - 2) { int mid = (l + r) >> 1; int mmid = (mid + r) >> 1; if (f(mid) > f(mmid)) { r = mmid; } else { l = mid; } } return max(f(l + 1), max(f(l), f(r))); } int main() { int q; int ch; ll number; cin >> q; for (int i = 1; i <= q; i++) { scanf("%d", &ch); if (ch == 1) { scanf("%lld", &number); num[++pop] = number; pre[pop] = pre[pop - 1] + number; } else { if (pop == 1) { cout << "0.00000000" << endl; continue; } if (pop == 2) { printf("%.9f ", (double)(num[2]) - ((double)num[2] + num[1]) / 2.0); continue; } l = 1, r = pop - 1; printf("%.9f ", SF()); } } return 0; }