Codeforces Round #510 (Div. 2)

A

二分

 1 #include<iostream>
 2 using namespace std;
 3 #define lson l,mid,rt<<1
 4 #define rson mid+1,r,rt<<1|1
 5 #define sqr(x) ((x)*(x))
 6 #define pb push_back
 7 #define eb emplace_back
 8 #define maxn 100005
 9 #define eps 1e-8
10 #define pi acos(-1.0)
11 #define rep(k,i,j) for(int k=i;k<j;k++)
12 typedef long long ll;
13 typedef pair<int,int> pii;
14 typedef pair<double,double>pdd;
15 typedef pair<int,char> pic;
16 typedef pair<pair<int,string>,pii> ppp;
17 typedef unsigned long long ull;
18 const long long MOD=1000000007;
19 const double oula=0.57721566490153286060651209;
20 using namespace std;
21 
22 int n;
23 int a[105];
24 int m;
25 
26 bool Check(int mid,int x){
27     for(int i=1;i<=n;i++){
28         x-=mid-a[i];
29     }
30     if(x>0) return true;
31     return false;
32 }
33 
34 int main(){
35     std::ios::sync_with_stdio(false);
36     cin>>n>>m;
37     int Max=0;
38     for(int i=1;i<=n;i++){
39         cin>>a[i];
40         Max=max(Max,a[i]);
41     }
42     int ans2=Max+m;
43     int L=Max,R=ans2,mid;
44     while(L<=R){
45         mid=L+R>>1;
46         if(Check(mid,m)){
47             L=mid+1;
48         }
49         else{
50             R=mid-1;
51         }
52     }
53     cout<<L<<" "<<ans2<<endl;
54 }

View Code

B

暴力模拟

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define lson l,mid,rt<<1
 4 #define rson mid+1,r,rt<<1|1
 5 #define sqr(x) ((x)*(x))
 6 #define pb push_back
 7 #define eb emplace_back
 8 #define maxn 100005
 9 #define eps 1e-8
10 #define pi acos(-1.0)
11 #define rep(k,i,j) for(int k=i;k<j;k++)
12 typedef long long ll;
13 typedef pair<int,int> pii;
14 typedef pair<double,double>pdd;
15 typedef pair<int,char> pic;
16 typedef pair<pair<int,string>,pii> ppp;
17 typedef unsigned long long ull;
18 const long long MOD=1000000007;
19 const double oula=0.57721566490153286060651209;
20 using namespace std;
21 
22 int n;
23 struct sair{
24     int v;
25     string s;
26 }a[1005];
27 
28 map<string,int>mp;
29 
30 int main(){
31     std::ios::sync_with_stdio(false);
32     cin>>n;
33     int flag=0;
34     mp["A"]=1000000;
35     mp["B"]=1000000;
36     mp["C"]=1000000;
37     mp["AB"]=1000000;
38     mp["AC"]=1000000;
39     mp["BC"]=1000000;
40     mp["ABC"]=1000000;
41     for(int i=1;i<=n;i++){
42         cin>>a[i].v>>a[i].s;
43         for(int j=0;j<a[i].s.length();j++){
44             flag|=(1<<(a[i].s[j]-'A'));
45         }
46         sort(a[i].s.begin(),a[i].s.end());
47         if(mp[a[i].s]>a[i].v) mp[a[i].s]=a[i].v;
48     }
49     if(flag!=7){
50         cout<<-1<<endl;
51     }
52     else{
53         int ans=0x3f3f3f3f;
54         ans=min(ans,min(mp["A"]+mp["B"]+mp["C"],min(mp["AB"]+mp["BC"],min(mp["AC"]+mp["BC"],min(mp["AB"]+mp["AC"],min(mp["ABC"],min(mp["A"]+mp["BC"],min(mp["B"]+mp["AC"],mp["C"]+mp["AB"]))))))));
55         cout<<ans<<endl;
56     }
57 
58 
59 }

View Code

C

题意：给n个数，每次使a[j]=a[i]*a[j],a[i]删除，使最后的数值最大。最多可以直接删除一个数字

思路：模拟。把正数，负数，零分别记录下标。如果负数的个数为偶数，就把它放到存放正数的vector里，否则取出一个最大的，把剩下的放到正数的vecotr里，然后把0和负数相乘后删除或直接删除负数，最后把正数相乘即可（打完才发现这是半年前遗留下来的题。。。）

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define lson l,mid,rt<<1
 4 #define rson mid+1,r,rt<<1|1
 5 #define sqr(x) ((x)*(x))
 6 #define pb push_back
 7 #define eb emplace_back
 8 #define maxn 100005
 9 #define eps 1e-8
10 #define pi acos(-1.0)
11 #define rep(k,i,j) for(int k=i;k<j;k++)
12 typedef long long ll;
13 typedef pair<int,int> pii;
14 typedef pair<double,double>pdd;
15 typedef pair<int,char> pic;
16 typedef pair<pair<int,string>,pii> ppp;
17 typedef unsigned long long ull;
18 const long long MOD=1000000007;
19 const double oula=0.57721566490153286060651209;
20 using namespace std;
21 
22 ll n;
23 ll a[200005];
24 vector<int>z;
25 vector<int>f;
26 vector<int>zero;
27 int ff=-1,zz=-1,ze=-1;
28 int main(){
29     std::ios::sync_with_stdio(false);
30     cin>>n;
31     for(int i=1;i<=n;i++){
32         cin>>a[i];
33         if(a[i]==0) zero.pb(i);
34         else if(a[i]>0) z.pb(i);
35         else f.pb(i);
36     }
37     if(f.size()%2){
38         int pos=0,Max=-0x3f3f3f3f;
39         for(int i=0;i<f.size();i++){
40             if(a[f[i]]>Max){
41                 Max=a[f[i]];
42                 pos=i;
43             }
44         }
45         ff=f[pos];
46         f[pos]=-1;
47         for(int i=0;i<f.size();i++){
48             if(f[i]!=-1){
49                 z.pb(f[i]);
50             }
51         }
52         f.clear();
53     }
54     else{
55         for(int i=0;i<f.size();i++){
56             z.pb(f[i]);
57         }
58         f.clear();
59     }
60     if(f.size()>=1) ff=f[0];
61     for(int i=1;i<f.size();i++){
62         cout<<1<<" "<<f[i]<<" "<<ff<<endl;
63     }
64     if(zero.size()>=1) ze=zero[0];
65     for(int i=1;i<zero.size();i++){
66         cout<<1<<" "<<zero[i]<<" "<<ze<<endl;
67     }
68     if(ff!=-1&&ze!=-1){
69         cout<<1<<" "<<ff<<" "<<ze<<endl;///ze
70     }
71     if(z.size()>0){
72         if(ff!=-1&&ze!=-1)
73             cout<<2<<" "<<ze<<endl;
74         else if(ff!=-1){
75             cout<<2<<" "<<ff<<endl;
76         }
77         else if(ze!=-1){
78             cout<<2<<" "<<ze<<endl;
79         }
80         zz=z[0];
81         for(int i=1;i<z.size();i++){
82             cout<<1<<" "<<z[i]<<" "<<zz<<endl;
83         }
84     }
85 
86 }

View Code

D

题意：给n个数，求一段区间和小于k

思路：看到区间和就会想到前缀和，然后可以发现一个公式：sum[r]-sum[l-1]<k 转换下：sum[r]-k<sum[l-1]

当我们遍历右端点时，可以发现，已知sum[r],k求sum[l-1] 就容易发现，这是一道可以用权值线段树求区间个数的题目

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define lson l,mid,rt<<1
 4 #define rson mid+1,r,rt<<1|1
 5 #define sqr(x) ((x)*(x))
 6 #define pb push_back
 7 #define eb emplace_back
 8 #define maxn 400005
 9 #define eps 1e-8
10 #define pi acos(-1.0)
11 #define rep(k,i,j) for(int k=i;k<j;k++)
12 typedef long long ll;
13 typedef pair<int,int> pii;
14 typedef pair<double,double>pdd;
15 typedef pair<int,char> pic;
16 typedef pair<pair<int,string>,pii> ppp;
17 typedef unsigned long long ull;
18 const long long MOD=1000000007;
19 const double oula=0.57721566490153286060651209;
20 using namespace std;
21 
22 ll n,t;
23 ll a[maxn];
24 ll b[maxn];
25 vector<ll>ve;
26 ll tree[maxn<<2];
27 
28 int getid(ll x){
29     return lower_bound(ve.begin(),ve.end(),x)-ve.begin()+1;
30 }
31 
32 void push_up(int rt){
33     tree[rt]=tree[rt<<1]+tree[rt<<1|1];
34 }
35 
36 void add(int L,int l,int r,int rt){
37    // cout<<L<<" "<<l<<" "<<r<<" "<<tree[rt]<<endl;
38     if(l==r) {
39         tree[rt]++;
40         return;
41     }
42     int mid=l+r>>1;
43     if(L<=mid) add(L,lson);
44     else add(L,rson);
45     push_up(rt);
46 }
47 
48 ll query(int L,int R,int l,int r,int rt){
49   //  cout<<L<<" "<<R<<" "<<l<<" "<<r<<" "<<tree[rt]<<endl;
50     if(L<=l&&R>=r){
51         return tree[rt];
52     }
53     int mid=l+r>>1;
54     ll ans=0;
55     if(L<=mid) ans+=query(L,R,lson);
56     if(R>mid) ans+=query(L,R,rson);
57     return ans;
58 }
59 
60 int main(){
61     std::ios::sync_with_stdio(false);
62     cin>>n>>t;
63     t--;
64     ll ans=0;
65     for(int i=1;i<=n;i++){
66         cin>>a[i];
67         b[i]=b[i-1]+a[i];
68     }
69     for(int i=1;i<=n;i++){
70         ve.pb(b[i]);
71         ve.pb(b[i]-t);
72     }
73     ve.pb(0);///**************************************
74     sort(ve.begin(),ve.end());
75     ve.erase(unique(ve.begin(),ve.end()),ve.end());
76     int N=ve.size();
77     int pos;
78   //  if(b[1]<=t) ans++;
79     add(getid(0),1,N,1);
80     for(int i=1;i<=n;i++){
81         pos=getid(b[i]-t);
82        // add(getid(b[i]),1,N,1);
83         ll tmp=query(pos,N,1,N,1);
84         add(getid(b[i]),1,N,1);
85         ans+=tmp;
86     }
87     cout<<ans<<endl;
88 }

View Code

E

题意：给n*m的矩阵，给出每个位置的权值，求从出发点出发，每次可以等概率的移动到一个权值小于当前点权值的点,同时得分加上两个点之间欧几里得距离的平方，问得分的期望

思路在代码里

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define lson l,mid,rt<<1
 4 #define rson mid+1,r,rt<<1|1
 5 #define sqr(x) ((x)*(x))
 6 #define pb push_back
 7 #define eb emplace_back
 8 #define maxn 1005
 9 #define eps 1e-8
10 #define pi acos(-1.0)
11 #define rep(k,i,j) for(int k=i;k<j;k++)
12 typedef long long ll;
13 typedef pair<int,int> pii;
14 typedef pair<double,double>pdd;
15 typedef pair<int,char> pic;
16 typedef pair<pair<int,string>,pii> ppp;
17 typedef unsigned long long ull;
18 const long long MOD=998244353;
19 const double oula=0.57721566490153286060651209;
20 using namespace std;
21 
22 ll n,m;
23 
24 struct sair{
25     int x,y,v;
26 }a[maxn*maxn];
27 
28 bool cmp(sair a,sair b){
29     return a.v<b.v;
30 }
31 
32 ll dp[maxn*maxn];
33 ll inv[maxn*maxn];
34 ll sum,sumdp,sumx,sumx2,sumy,sumy2;
35 /**状态转移方程：dp[i]=sum(dp[j]+(x[i]-x[j])^2+(y[i]-y[j])^2)/s
36 展开后:dp[i]=sum(dp[j]+x[i]^2-2*x[i]x[j]+x[j]^2+y[i]^2-2*y[i]y[j]+y[j]^2)/s
37 令sumdp=sum(dp[j]),sumx=sum(sum[j]),sumx2=sum(sum[j]*sum[j])
38 sumy,sumy2同理
39 转换下：dp[i]=(sumf+sum*x[i]*x[i]-2*x[i]*sumx+sumx2+sum*y[i]*y[i]-2*y[i]*sumy+sumy*sumy)/s;
40 sum变量为比它小的个数
41 */
42 int main(){
43     std::ios::sync_with_stdio(false);
44     cin>>n>>m;
45     int x,y;
46     for(int i=1;i<=n;i++){
47         for(int j=1;j<=m;j++){
48             cin>>a[(i-1)*m+j].v;
49             a[(i-1)*m+j].x=i;
50             a[(i-1)*m+j].y=j;
51         }
52     }
53     cin>>x>>y;
54     n*=m;
55     sort(a+1,a+n+1,cmp);
56     inv[1]=1;
57     for(int i=2;i<=n;i++) inv[i]=(-MOD/i*inv[MOD%i])%MOD;///求逆元
58     a[n+1].v=-1;
59     for(int i=1;i<=n;i++){
60         if(sum){
61             dp[i]=((dp[i]+((sum*a[i].x*a[i].x)%MOD-2*sumx*a[i].x%MOD+sumx2)%MOD)+MOD)%MOD;
62             dp[i]=((dp[i]+((sum*a[i].y*a[i].y)%MOD-2*sumy*a[i].y%MOD+sumy2)%MOD)+MOD)%MOD;
63             dp[i]=(dp[i]+sumdp)%MOD;
64             dp[i]=dp[i]*inv[sum]%MOD;
65         }
66         else{
67             dp[i]=0;
68         }
69         if(a[i].x==x&&a[i].y==y){
70             cout<<(dp[i]+MOD)%MOD<<endl;
71             break;
72         }
73         if(a[i].v!=a[i+1].v){
74             for(int j=i;j;j--){
75                 if(a[j].v!=a[i].v) break;
76                 sumdp=(sumdp+dp[j])%MOD;
77                 sumx=(sumx+a[j].x)%MOD;
78                 sumx2=(sumx2+(a[j].x)*a[j].x)%MOD;
79                 sumy=(sumy+a[j].y)%MOD;
80                 sumy2=(sumy2+a[j].y*a[j].y)%MOD;
81                 sum++;
82             }
83         }
84     }
85 }

View Code

F

题意：给你一棵树，求它所有叶子节点最少可以划分为多少个集合，划分的依据为集合内的叶子节点两两之间的距离不超过k

思路：这题用逆向思维。父节点存叶子节点的距离，当距离最大的两个叶子节点之和超过k时，就需要多划分一个集合

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define lson l,mid,rt<<1
 4 #define rson mid+1,r,rt<<1|1
 5 #define sqr(x) ((x)*(x))
 6 #define pb push_back
 7 #define eb emplace_back
 8 #define maxn 3000006
 9 #define eps 1e-8
10 #define pi acos(-1.0)
11 #define rep(k,i,j) for(int k=i;k<j;k++)
12 typedef long long ll;
13 typedef pair<int,int> pii;
14 typedef pair<double,double>pdd;
15 typedef pair<int,char> pic;
16 typedef pair<pair<int,string>,pii> ppp;
17 typedef unsigned long long ull;
18 const long long MOD=1000000007;
19 const double oula=0.57721566490153286060651209;
20 using namespace std;
21 
22 vector<int>ve[maxn];
23 bool vis[maxn];
24 int n,k;
25 int ans=1;
26 
27 int dfs(int now){
28     vector<int>tmp;
29     vis[now]=1;
30     if(ve[now].size()==1) return 0;
31     for(int i=0;i<ve[now].size();i++){
32         if(!vis[ve[now][i]]){
33             tmp.pb(dfs(ve[now][i])+1);
34         }
35     }
36     sort(tmp.begin(),tmp.end());
37     while(tmp.size()>1){
38         if(tmp[tmp.size()-1]+tmp[tmp.size()-2]<=k) break;
39         ans++;
40         tmp.pop_back();
41     }
42     return tmp[tmp.size()-1];
43 }
44 
45 int main(){
46     std::ios::sync_with_stdio(false);
47     cin>>n>>k;
48     int x,y;
49     for(int i=1;i<n;i++){
50         cin>>x>>y;
51         ve[x].pb(y);
52         ve[y].pb(x);
53     }
54     for(int i=1;i<=n;i++){
55         if(ve[i].size()>1){
56             dfs(i);
57             break;
58         }
59     }
60     cout<<ans<<endl;
61 }

View Code