Codeforces Round #510 (Div. 2)

A

二分

 #include<iostream>

 using namespace std;

 #define lson l,mid,rt<<1

 #define rson mid+1,r,rt<<1|1

 #define sqr(x) ((x)*(x))

 #define pb push_back

 #define eb emplace_back

 #define maxn 100005

 #define eps 1e-8

 #define pi acos(-1.0)

 #define rep(k,i,j) for(int k=i;k<j;k++)

 typedef long long ll;

 typedef pair<int,int> pii;

 typedef pair<double,double>pdd;

 typedef pair<int,char> pic;

 typedef pair<pair<int,string>,pii> ppp;

 typedef unsigned long long ull;

 const long long MOD=;

 const double oula=0.57721566490153286060651209;

 using namespace std;

 int n;

 int a[];

 int m;

 bool Check(int mid,int x){

     for(int i=;i<=n;i++){

         x-=mid-a[i];

     }

     if(x>) return true;

     return false;

 }

 int main(){

     std::ios::sync_with_stdio(false);

     cin>>n>>m;

     int Max=;

     for(int i=;i<=n;i++){

         cin>>a[i];

         Max=max(Max,a[i]);

     }

     int ans2=Max+m;

     int L=Max,R=ans2,mid;

     while(L<=R){

         mid=L+R>>;

         if(Check(mid,m)){

             L=mid+;

         }

         else{

             R=mid-;

         }

     }

     cout<<L<<" "<<ans2<<endl;

 }

B

暴力模拟

 #include<bits/stdc++.h>

 using namespace std;

 #define lson l,mid,rt<<1

 #define rson mid+1,r,rt<<1|1

 #define sqr(x) ((x)*(x))

 #define pb push_back

 #define eb emplace_back

 #define maxn 100005

 #define eps 1e-8

 #define pi acos(-1.0)

 #define rep(k,i,j) for(int k=i;k<j;k++)

 typedef long long ll;

 typedef pair<int,int> pii;

 typedef pair<double,double>pdd;

 typedef pair<int,char> pic;

 typedef pair<pair<int,string>,pii> ppp;

 typedef unsigned long long ull;

 const long long MOD=;

 const double oula=0.57721566490153286060651209;

 using namespace std;

 int n;

 struct sair{

     int v;

     string s;

 }a[];

 map<string,int>mp;

 int main(){

     std::ios::sync_with_stdio(false);

     cin>>n;

     int flag=;

     mp["A"]=;

     mp["B"]=;

     mp["C"]=;

     mp["AB"]=;

     mp["AC"]=;

     mp["BC"]=;

     mp["ABC"]=;

     for(int i=;i<=n;i++){

         cin>>a[i].v>>a[i].s;

         for(int j=;j<a[i].s.length();j++){

             flag|=(<<(a[i].s[j]-'A'));

         }

         sort(a[i].s.begin(),a[i].s.end());

         if(mp[a[i].s]>a[i].v) mp[a[i].s]=a[i].v;

     }

     if(flag!=){

         cout<<-<<endl;

     }

     else{

         int ans=0x3f3f3f3f;

         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"]))))))));

         cout<<ans<<endl;

     }

 }

C

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

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

 #include<bits/stdc++.h>

 using namespace std;

 #define lson l,mid,rt<<1

 #define rson mid+1,r,rt<<1|1

 #define sqr(x) ((x)*(x))

 #define pb push_back

 #define eb emplace_back

 #define maxn 100005

 #define eps 1e-8

 #define pi acos(-1.0)

 #define rep(k,i,j) for(int k=i;k<j;k++)

 typedef long long ll;

 typedef pair<int,int> pii;

 typedef pair<double,double>pdd;

 typedef pair<int,char> pic;

 typedef pair<pair<int,string>,pii> ppp;

 typedef unsigned long long ull;

 const long long MOD=;

 const double oula=0.57721566490153286060651209;

 using namespace std;

 ll n;

 ll a[];

 vector<int>z;

 vector<int>f;

 vector<int>zero;

 int ff=-,zz=-,ze=-;

 int main(){

     std::ios::sync_with_stdio(false);

     cin>>n;

     for(int i=;i<=n;i++){

         cin>>a[i];

         if(a[i]==) zero.pb(i);

         else if(a[i]>) z.pb(i);

         else f.pb(i);

     }

     if(f.size()%){

         int pos=,Max=-0x3f3f3f3f;

         for(int i=;i<f.size();i++){

             if(a[f[i]]>Max){

                 Max=a[f[i]];

                 pos=i;

             }

         }

         ff=f[pos];

         f[pos]=-;

         for(int i=;i<f.size();i++){

             if(f[i]!=-){

                 z.pb(f[i]);

             }

         }

         f.clear();

     }

     else{

         for(int i=;i<f.size();i++){

             z.pb(f[i]);

         }

         f.clear();

     }

     if(f.size()>=) ff=f[];

     for(int i=;i<f.size();i++){

         cout<<<<" "<<f[i]<<" "<<ff<<endl;

     }

     if(zero.size()>=) ze=zero[];

     for(int i=;i<zero.size();i++){

         cout<<<<" "<<zero[i]<<" "<<ze<<endl;

     }

     if(ff!=-&&ze!=-){

         cout<<<<" "<<ff<<" "<<ze<<endl;///ze

     }

     if(z.size()>){

         if(ff!=-&&ze!=-)

             cout<<<<" "<<ze<<endl;

         else if(ff!=-){

             cout<<<<" "<<ff<<endl;

         }

         else if(ze!=-){

             cout<<<<" "<<ze<<endl;

         }

         zz=z[];

         for(int i=;i<z.size();i++){

             cout<<<<" "<<z[i]<<" "<<zz<<endl;

         }

     }

 }

D

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

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

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

 #include<bits/stdc++.h>

 using namespace std;

 #define lson l,mid,rt<<1

 #define rson mid+1,r,rt<<1|1

 #define sqr(x) ((x)*(x))

 #define pb push_back

 #define eb emplace_back

 #define maxn 400005

 #define eps 1e-8

 #define pi acos(-1.0)

 #define rep(k,i,j) for(int k=i;k<j;k++)

 typedef long long ll;

 typedef pair<int,int> pii;

 typedef pair<double,double>pdd;

 typedef pair<int,char> pic;

 typedef pair<pair<int,string>,pii> ppp;

 typedef unsigned long long ull;

 const long long MOD=;

 const double oula=0.57721566490153286060651209;

 using namespace std;

 ll n,t;

 ll a[maxn];

 ll b[maxn];

 vector<ll>ve;

 ll tree[maxn<<];

 int getid(ll x){

     return lower_bound(ve.begin(),ve.end(),x)-ve.begin()+;

 }

 void push_up(int rt){

     tree[rt]=tree[rt<<]+tree[rt<<|];

 }

 void add(int L,int l,int r,int rt){

    // cout<<L<<" "<<l<<" "<<r<<" "<<tree[rt]<<endl;

     if(l==r) {

         tree[rt]++;

         return;

     }

     int mid=l+r>>;

     if(L<=mid) add(L,lson);

     else add(L,rson);

     push_up(rt);

 }

 ll query(int L,int R,int l,int r,int rt){

   //  cout<<L<<" "<<R<<" "<<l<<" "<<r<<" "<<tree[rt]<<endl;

     if(L<=l&&R>=r){

         return tree[rt];

     }

     int mid=l+r>>;

     ll ans=;

     if(L<=mid) ans+=query(L,R,lson);

     if(R>mid) ans+=query(L,R,rson);

     return ans;

 }

 int main(){

     std::ios::sync_with_stdio(false);

     cin>>n>>t;

     t--;

     ll ans=;

     for(int i=;i<=n;i++){

         cin>>a[i];

         b[i]=b[i-]+a[i];

     }

     for(int i=;i<=n;i++){

         ve.pb(b[i]);

         ve.pb(b[i]-t);

     }

     ve.pb();///**************************************

     sort(ve.begin(),ve.end());

     ve.erase(unique(ve.begin(),ve.end()),ve.end());

     int N=ve.size();

     int pos;

   //  if(b[1]<=t) ans++;

     add(getid(),,N,);

     for(int i=;i<=n;i++){

         pos=getid(b[i]-t);

        // add(getid(b[i]),1,N,1);

         ll tmp=query(pos,N,,N,);

         add(getid(b[i]),,N,);

         ans+=tmp;

     }

     cout<<ans<<endl;

 }

E

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

思路在代码里

 #include<bits/stdc++.h>

 using namespace std;

 #define lson l,mid,rt<<1

 #define rson mid+1,r,rt<<1|1

 #define sqr(x) ((x)*(x))

 #define pb push_back

 #define eb emplace_back

 #define maxn 1005

 #define eps 1e-8

 #define pi acos(-1.0)

 #define rep(k,i,j) for(int k=i;k<j;k++)

 typedef long long ll;

 typedef pair<int,int> pii;

 typedef pair<double,double>pdd;

 typedef pair<int,char> pic;

 typedef pair<pair<int,string>,pii> ppp;

 typedef unsigned long long ull;

 const long long MOD=;

 const double oula=0.57721566490153286060651209;

 using namespace std;

 ll n,m;

 struct sair{

     int x,y,v;

 }a[maxn*maxn];

 bool cmp(sair a,sair b){

     return a.v<b.v;

 }

 ll dp[maxn*maxn];

 ll inv[maxn*maxn];

 ll sum,sumdp,sumx,sumx2,sumy,sumy2;

 /**状态转移方程：dp[i]=sum(dp[j]+(x[i]-x[j])^2+(y[i]-y[j])^2)/s

 展开后: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

 令sumdp=sum(dp[j]),sumx=sum(sum[j]),sumx2=sum(sum[j]*sum[j])

 sumy,sumy2同理

 转换下：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;

 sum变量为比它小的个数

 */

 int main(){

     std::ios::sync_with_stdio(false);

     cin>>n>>m;

     int x,y;

     for(int i=;i<=n;i++){

         for(int j=;j<=m;j++){

             cin>>a[(i-)*m+j].v;

             a[(i-)*m+j].x=i;

             a[(i-)*m+j].y=j;

         }

     }

     cin>>x>>y;

     n*=m;

     sort(a+,a+n+,cmp);

     inv[]=;

     for(int i=;i<=n;i++) inv[i]=(-MOD/i*inv[MOD%i])%MOD;///求逆元

     a[n+].v=-;

     for(int i=;i<=n;i++){

         if(sum){

             dp[i]=((dp[i]+((sum*a[i].x*a[i].x)%MOD-*sumx*a[i].x%MOD+sumx2)%MOD)+MOD)%MOD;

             dp[i]=((dp[i]+((sum*a[i].y*a[i].y)%MOD-*sumy*a[i].y%MOD+sumy2)%MOD)+MOD)%MOD;

             dp[i]=(dp[i]+sumdp)%MOD;

             dp[i]=dp[i]*inv[sum]%MOD;

         }

         else{

             dp[i]=;

         }

         if(a[i].x==x&&a[i].y==y){

             cout<<(dp[i]+MOD)%MOD<<endl;

             break;

         }

         if(a[i].v!=a[i+].v){

             for(int j=i;j;j--){

                 if(a[j].v!=a[i].v) break;

                 sumdp=(sumdp+dp[j])%MOD;

                 sumx=(sumx+a[j].x)%MOD;

                 sumx2=(sumx2+(a[j].x)*a[j].x)%MOD;

                 sumy=(sumy+a[j].y)%MOD;

                 sumy2=(sumy2+a[j].y*a[j].y)%MOD;

                 sum++;

             }

         }

     }

 }

F

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

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

 #include<bits/stdc++.h>

 using namespace std;

 #define lson l,mid,rt<<1

 #define rson mid+1,r,rt<<1|1

 #define sqr(x) ((x)*(x))

 #define pb push_back

 #define eb emplace_back

 #define maxn 3000006

 #define eps 1e-8

 #define pi acos(-1.0)

 #define rep(k,i,j) for(int k=i;k<j;k++)

 typedef long long ll;

 typedef pair<int,int> pii;

 typedef pair<double,double>pdd;

 typedef pair<int,char> pic;

 typedef pair<pair<int,string>,pii> ppp;

 typedef unsigned long long ull;

 const long long MOD=;

 const double oula=0.57721566490153286060651209;

 using namespace std;

 vector<int>ve[maxn];

 bool vis[maxn];

 int n,k;

 int ans=;

 int dfs(int now){

     vector<int>tmp;

     vis[now]=;

     if(ve[now].size()==) return ;

     for(int i=;i<ve[now].size();i++){

         if(!vis[ve[now][i]]){

             tmp.pb(dfs(ve[now][i])+);

         }

     }

     sort(tmp.begin(),tmp.end());

     while(tmp.size()>){

         if(tmp[tmp.size()-]+tmp[tmp.size()-]<=k) break;

         ans++;

         tmp.pop_back();

     }

     return tmp[tmp.size()-];

 }

 int main(){

     std::ios::sync_with_stdio(false);

     cin>>n>>k;

     int x,y;

     for(int i=;i<n;i++){

         cin>>x>>y;

         ve[x].pb(y);

         ve[y].pb(x);

     }

     for(int i=;i<=n;i++){

         if(ve[i].size()>){

             dfs(i);

             break;

         }

     }

     cout<<ans<<endl;

 }

秒客网

Codeforces Round #510 (Div. 2)

Codeforces Round #510 (Div. 2)

A

B

C

D

E

F

相关文章