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-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 maxm = 300; 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 = 3e7; const int maxn = 200005; int main() { int n, m; while (cin >> n >> m) { int mid = (n + m) / 2; //cout<<mid<<endl; int x1 = abs(mid - n); int x2 = abs(m - mid); int ans = (1 + x1) * x1 / 2 + (1 + x2) * x2 / 2; cout << ans << endl; } }
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() { int n; cin >> n; int a, b; cin >> a >> b; if (a > b) { swap(a, b); } if (a <= n / 2 && b > n / 2) { cout << "Final!" << endl; return 0; } int anser = 1; while (true) { a = (a + (a % 2)) / 2; b = (b + (b % 2)) / 2; if (a == b) { cout << anser << endl; return 0; } anser++; } 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 maxm = 300; 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 = 3e7; const int maxn = 200005; int num[100005]; int anser; int main() { int mx=-100005; int mn=100005; int mxnum=0; int mnnum=0; int n; cin >> n; anser=n; for(int i=1; i<=n; i++) { scanf("%d",&num[i]); mx=max(mx,num[i]); mn=min(mn,num[i]); } if(mx-mn<=1) { cout<<n<<endl; for(int i=1; i<=n; i++) cout<<num[i]<<" "; cout<<endl; return 0; } for(int i=1; i<=n; i++) { if(num[i]==mx) mxnum++; else if(num[i]==mn) mnnum++; } int midnum=n-mxnum-mnnum; if(midnum/2>=min(mxnum,mnnum)) { int cur=midnum/2; int cur1=cur; for(int i=1; i<=n; i++) { if(num[i]==mn+1&&cur) { anser--; num[i]--; cur--; continue; } if(num[i]==mn+1&&cur1) { anser--; num[i]++; cur1--; continue; } } } else { int cur=min(mxnum,mnnum); int cur1=cur; for(int i=1;i<=n;i++) { if(num[i]==mn&&cur) { num[i]++; anser--; cur--; continue; } if(num[i]==mx&&cur1) { num[i]--; anser--; cur1--; continue; } } } cout<<anser<<endl; for(int i=1;i<=n;i++) cout<<num[i]<<" "; cout<<endl; }
D
思维题 一层一层地消
#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 maxm = 300; 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 = 3e7; const int maxn = 200005; int nextt[100005]; int num[100005]; int level[100005]; int dp[100005]; int anser = 0; int main() { int n; cin >> n; dp[1] = level[1] = dp[1] = 1; for (int i = 2; i <= n; i++) { scanf("%d", &nextt[i]); dp[i] = dp[nextt[i]] + 1; level[dp[i]]++; } for(int i=1;i<=100000;i++) { if(level[i]&1) anser++; } cout<<anser<<endl; return 0; }
E
状压DP
dp[i][j][k]表示第一个字母是i第二个字母是j距离为k有多少个
因为第一个字母是由第一个玩家定的 所以无法选择 第二个字母可以选择但只能最优地选一次 所以ans+=now 取所有长度里面概率最高的
#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; typedef pair<int, int> pairint; typedef long long ll; typedef unsigned long long ull; //const int maxn = 3e5 + 10; const int maxn = 100005; const int turn[4][2] = {{1, 0}, { -1, 0}, {0, 1}, {0, -1}}; const int turn2[8][2] = {{1, 0}, { -1, 0}, {0, 1}, {0, -1}, {1, -1}, { -1, -1}, {1, 1}, { -1, 1}}; //priority_queue<int, vector<int>, less<int>> que; //next_permutation char a[10005]; int dp[30][30][5005]; int anser = 0; int main() { scanf("%s", a + 1); int len = strlen(a + 1); for (int i = 1; i <= len; i++) { a[i + len] = a[i]; } for (int i = 1; i <= len; i++) { for (int j = i + 1; j < i + len; j++) { dp[a[i] - 'a'][a[j] - 'a'][j - i + 1]++; } } int now = 0; int cur; for (int i = 0; i < 26; i++) { now = 0; for (int j = 2; j <= len; j++) { cur = 0; for (int k = 0; k < 26; k++) { if (dp[i][k][j] == 1) { cur++; } } now = max(now, cur); } anser += now; } printf("%.10f", (double)anser / len); return 0; }
F
待补