A. Distance
B. Special Permutation
C. Chat Ban
D.X-Magic Pair
E. Messages
F：沒看F，好難的樣子
G. Max Sum Array

#include <iostream> #include <algorithm> #include <cstring> #include <vector> #include <cmath> #include <stack> #include <map> #define mid (l+r>>1) #define lowbit(x) (x&-x) using namespace std; typedef long long LL; typedef pair<int,int> PII; const int N = 1e5, M = 5e2;int main() {int t;scanf("%d", &t);while(t --){int a, b;scanf("%d%d", &a, &b);if(abs(a)+abs(b)&1)puts("-1 -1");else{int x = abs(a)>>1, y = (abs(a)+abs(b)>>1)-x;if(a<0)x=-x;if(b<0)y=-y;cout<<x<<' '<<y<<endl;}}return 0; }

硬模擬

#include <iostream> #include <algorithm> #include <cstring> #include <vector> #include <cmath> #include <stack> #include <map> #define mid (l+r>>1) #define lowbit(x) (x&-x) using namespace std; typedef long long LL; typedef pair<int,int> PII; const int N = 1e5, M = 5e2;int main() {int t;scanf("%d", &t);while(t --){int n, a, b, l = 1, r = 2, pos[N]={0}, nl = 0, nr = 0;bool f = 0;scanf("%d%d%d", &n, &a, &b);for(int i = n;i > b;i --)pos[i] = l, nl++;if(!pos[a])pos[a] = l, nl++;for(int i = 1;i < a;i ++)f |= pos[i] == l, pos[i] = r, nr++;if(!pos[b]) f |= pos[b] == l, pos[b] = r, nr++;for(int i = a+1;i < b;i ++)if(!pos[i]){if(nl < n/2)pos[i] = l, nl++;else pos[i] = r;}if(f || nl!=n/2)puts("-1");else{for(int i = 1;i <= n;i ++)if(pos[i] == l)cout<<i<<' ';for(int i = 1;i <= n;i ++)if(pos[i] == r)cout<<i<<' ';puts("");}}return 0; }

二分直接算

#include <iostream> #include <algorithm> #include <cstring> #include <vector> #include <cmath> #include <stack> #include <map> #define mid (l+r>>1) #define lowbit(x) (x&-x) using namespace std; typedef long long LL; typedef pair<int,int> PII; const int N = 1e5, M = 5e2;LL k, x;bool ch(LL l) {LL sum = 0;if(l>k) sum = (1+k)*k/2 + (k+2*k-l-1)*(l-k)/2;else sum = (1+l)*l/2;return sum>=x; } int main() {int t;scanf("%d", &t);while(t --){scanf("%lld%lld", &k, &x);LL l = 1, r = 2*k-1;while(l < r){if(ch(mid)) r=mid;else l=mid+1;}cout<<l<<endl;}return 0; }

隊(duì)友寫的，沒搞懂

#include <iostream> #include <algorithm> #include <cstring> #include <vector> #include <cmath> #include <stack> #include <map> #define mid (l+r>>1) #define lowbit(x) (x&-x) using namespace std; typedef long long LL; typedef pair<int,int> PII; const int N = 1e5, M = 5e2;int main() {int t;scanf("%d", &t);while(t --){LL a, b, x;bool f = 0;scanf("%lld%lld%lld", &a, &b, &x);if(x<=max(a, b)){while(a>=x||b>=x&&a&&b){if(a<b)swap(a, b);if(a==x||b==x||(a-x)%b==0){f = 1;break;}a %= b;}}puts(f?"YES":"NO");}return 0; }

?概率公式計(jì)算，假設(shè)有n張牌，其中里面有他要的，它可以抽k張牌，如果k>n那么這個(gè)人的期望就是n/n，否則是1 - $\left(\genfrac{}{}{0ex}{}{n?1}{k}\right)$/$\left(\genfrac{}{}{0ex}{}{n}{k}\right)$ = k / n。
?然后可以枚舉小于20的n枚舉的時(shí)候k大于n的貢獻(xiàn)要變成1。
?對于大于20的n來說答案就可以按照期望貢獻(xiàn)對數(shù)字排序，再進(jìn)行遞推枚舉計(jì)算。
具體看代碼

#include <iostream> #include <algorithm> #include <cstring> #include <vector> #include <cmath> #include <stack> #include <map> #define mid (l+r>>1) #define lowbit(x) (x&-x) using namespace std; typedef long long LL; typedef pair<int,int> PII; const int N = 2e5+10, M = 5e2;int a[N][21]; PII b[N]; vector<int>ans;int main() {int n;scanf("%d", &n);for(int i = 1;i <= n;i ++){int x, y;scanf("%d%d", &x, &y);a[x][y]++; //有個(gè) 數(shù)字為x，k等于y的人 }LL ma = 0, mn = 1; // ma 是最大值， mn是最大值個(gè)數(shù)其實(shí)在ans-vector里有體現(xiàn)； for(int i = 1;i <= 20;i ++){ // 枚舉n for(int j = 1;j <= 2e5;j ++){ // 遍歷每個(gè)樹 int sum = 0; // 當(dāng)n等于i時(shí)數(shù)字i對于期望的貢獻(xiàn) for(int k = 1;k <= i;k ++)sum += a[j][k]*k; // k ＜ n時(shí) k = k， k ≥n時(shí) k = n； for(int k = i+1;k <= 20;k ++)sum += a[j][k]*i;b[j] = {-sum, j}; // 第一關(guān)鍵字取反按照從小往大排序的話第一個(gè)取反就是最大值； }sort(b+1, b+(int)2e5+1); LL sum = 0;for(int x = 1;x <= i;x ++)sum += -b[x].first;if(sum*mn>ma*i){ // 分式化乘法 ans.clear();for(int x = 1;x <= i;x ++)ans.push_back(b[x].second);ma = sum; mn = i;} }LL h = 0;for(int i = 1;i <= 20&&i <= n;i ++)h += -b[i].first; // 這時(shí)候是先求出前二十個(gè)的和； for(int i = 21;i <= n;i ++) // 枚舉21 - n 的個(gè)數(shù)取值； {h += -b[i].first;if(h*mn>ma*i)ma = h, mn = i;}if(mn > 20)for(int i = 1;i <= mn;i ++)ans.push_back(b[i].second);cout<<ans.size()<<endl;for(auto x: ans)cout<<x<<' ';cout<<endl;return 0; }

? 沒人補(bǔ)G嗎，假設(shè)有n個(gè)相等數(shù)字且位置為P1 P2 P3 …Pn，那么你計(jì)算之后就可以得到 ${\sum }_{i=1}^n$ ( 2 $?$ i - n -1) $?$ Pi

? 那么再對于每個(gè)n都確定前面的 ( 2 $?$ i - n -1)，那么這個(gè)東西就由 Pi 確定，然后可以看出( 2 $?$ i - n -1)要么都是奇數(shù)要么都是偶數(shù)那么再把不連續(xù)的變成連續(xù)的(這步在代碼里面有注釋), 再挨個(gè)計(jì)算，數(shù)量就是( 2 $?$ i - n -1)相等的數(shù)量的階乘的乘積

#include <iostream> #include <algorithm> #include <cstring> #include <vector> #include <cmath> #include <stack> #include <set> #define mid (l+r>>1) #define lowbit(x) (x&-x) using namespace std; typedef long long LL; typedef pair<int,int> PII; const int N = 2e6+10, mod = 1e9 + 7; void mull(int &a, LL b){a = a*b%mod;return ;} void add(int &a, LL b){a = (a+b)%mod;return ;}LL a[N], b[N], in[N]; // a ：-2 0 2 4 6 -> -1 0 1 2 3 n 是奇數(shù) // b ：-3 -1 1 3 -> -2 0 2 4 < a n 是偶數(shù) LL se(LL a, int b){a%=mod;return b*(a+a+b-1)%mod*500000004%mod;}int main() {int n;scanf("%d", &n);in[0] = 1;for(int i = 1;i <= n;i ++){int x;scanf("%d", &x);LL *t = a, f = 0;if(x%2 == 0)t = b, f = 1;t[(1-x+f)/2+(int)1e6]++;t[(x-1+f)/2+(int)1e6+1]--;in[i] = i*in[i-1]%mod;}int ans = 0, sum = 1;LL head = 1;for(int i = 0;i <= 2e6;i ++){a[i] += a[i-1]; b[i] += b[i-1];add(ans, ((i-(int)1e6)*2-1)*se(head, b[i])%mod);head += b[i];add(ans, ((i-(int)1e6)*2)*se(head, a[i])%mod);head += a[i];mull(sum, in[b[i]]*in[a[i]]%mod);}add(ans, mod);cout<<ans<<' '<<sum<<endl;return 0; }

總結(jié)

以上是生活随笔為你收集整理的Educational Codeforces Round 117 (Rated for Div. 2)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。