2019东北四省B,G,H,J 2018宁夏 A，F

今天药忘吃喽~ 2022-01-07 06:03 133阅读 0赞

[The 13th Chinese Northeast Collegiate Programming Contest][]

B. Balanced Diet

#include<bits/stdc++.h>
    #define il inline
    #define pb push_back
    #define fi first
    #define se second
    #define ms(_data,v) memset(_data,v,sizeof(_data))
    #define sc(n) scanf("%d",&n)
    #define SC(n,m) scanf("%d %d",&n,&m)
    #define SZ(a) int((a).size())
    #define rep(i,a,b) for(int i=a;i<=b;++i)
    #define drep(i,a,b)	for(int i=a;i>=b;--i)
    using namespace std;
    typedef long long ll;
    const ll inf=0x3f3f3f3f;
    const double PI=acos(-1.0);
    const double eps=1e-9;
    const int maxn=1e5+5;
    int T,n,m,l[maxn];
    vector<int> v[maxn],f[maxn];
    bool cmp(int x,int y)	{return x>y;}
    int main(){
    	std::ios::sync_with_stdio(0);
    	cin>>T;
    	while(T--){
    		cin>>n>>m;
    		rep(i,1,m)	cin>>l[i];
    		int val,op;
    		rep(i,1,n){
    			cin>>val>>op;
    			v[op].pb(val);
    		}
    		rep(i,1,m){
    			sort(v[i].begin(),v[i].end(),cmp);
    			rep(j,0,SZ(v[i])-1)	f[max((j+1),l[i])].pb(v[i][j]);
    			v[i].clear();
    		}
    		ll as=0,ac=1,ns=0,nc;
    		rep(i,1,n){
    			nc=i;
    			rep(j,0,SZ(f[i])-1)	ns+=f[i][j];
    			if(ns*ac > nc*as)	as=ns,ac=nc;
    			f[i].clear();
    		}
    		ll tp=__gcd(ac,as);
    		cout<<as/tp<<"/"<<ac/tp<<endl;
    		
    	}
    	return 0;
    }

G. Radar Scanner

#include<bits/stdc++.h>
    #define il inline
    #define pb push_back
    #define fi first
    #define se second
    #define ms(_data,v) memset(_data,v,sizeof(_data))
    #define sc(n) scanf("%d",&n)
    #define SC(n,m) scanf("%d %d",&n,&m)
    #define SZ(a) int((a).size())
    #define rep(i,a,b) for(int i=a;i<=b;++i)
    #define drep(i,a,b)	for(int i=a;i>=b;--i)
    using namespace std;
    typedef long long ll;
    const ll inf=0x3f3f3f3f;
    const double PI=acos(-1.0);
    const double eps=1e-9;
    const int maxn=1e6+5;
    struct node{
    	int x1,y1,x2,y2;
    }a[maxn];
    int T,n;
    vector<int> tx,ty;
    int main(){
    	std::ios::sync_with_stdio(0);
    	cin>>T;
    	while(T--){
    		tx.clear(),ty.clear();
    		cin>>n;
    		rep(i,1,n){
    			cin>>a[i].x1>>a[i].y1>>a[i].x2>>a[i].y2;
    			tx.pb(a[i].x1),tx.pb(a[i].x2);
    			ty.pb(a[i].y1),ty.pb(a[i].y2);
    		}
    		sort(tx.begin(),tx.end());
    		sort(ty.begin(),ty.end());
    		int sx=SZ(tx),sy=SZ(ty);
    		int midx=(tx[sx/2]+tx[sx/2-1])/2;
    		int midy=(ty[sy/2]+ty[sy/2-1])/2;
    		ll ans=0;
    		rep(i,1,n){
    			ans+=(abs(midx-a[i].x1)+abs(midx-a[i].x2)-(a[i].x2-a[i].x1))/2;
    			ans+=(abs(midy-a[i].y1)+abs(midy-a[i].y2)-(a[i].y2-a[i].y1))/2;
    		}
    		cout<<ans<<endl;
    	}
    	
    	return 0;
    }

H. Skyscraper

#include<bits/stdc++.h>
    #define il inline
    #define pb push_back
    #define fi first
    #define se second
    #define ms(_data,v) memset(_data,v,sizeof(_data))
    #define sc(n) scanf("%d",&n)
    #define SC(n,m) scanf("%d %d",&n,&m)
    #define SZ(a) int((a).size())
    #define rep(i,a,b) for(int i=a;i<=b;++i)
    #define drep(i,a,b)	for(int i=a;i>=b;--i)
    using namespace std;
    typedef long long ll;
    const ll inf=0x3f3f3f3f;
    const double PI=acos(-1.0);
    const double eps=1e-9;
    const int maxn=1e6+6;
    ll T,n,m,a[maxn],b[maxn];
    struct tr {
    	ll sum[maxn];
    	void add(int p,int x) {
    		while(p<=n+2)	sum[p]+=x,p+=p&-p;
    	}
    	ll ask(int p) {
    		ll res=0;
    		while(p)	res+=sum[p],p-=p&-p;
    		return res;
    	}
    	ll r_ask(int l,int r) {
    		return ask(r)-ask(l-1);
    	}
    } tb,tc;
    int main() {
    	std::ios::sync_with_stdio(0);
    	cin>>T;
    	while(T--) {
    		cin>>n>>m;
    		rep(i,1,n) {
    			cin>>a[i];
    			if(i>=2) {
    				b[i]=a[i]-a[i-1];
    				tb.add(i,b[i]);
    				if(b[i]>0) tc.add(i,b[i]);
    			} 
    			else {
    				b[i]=a[i];
    				tb.add(i,a[i]);
    				tc.add(i,a[i]);
    			}
    		}
    		int op,l,r,x;
    		rep(i,1,m) {
    			cin>>op;
    			if(op==1) {
    				cin>>l>>r>>x;
    				tb.add(l,x),tb.add(r+1,-x);
    				if(b[l]>0) 	tc.add(l,x);
    				else if(b[l]+x>0) tc.add(l,b[l]+x);
    				
    				if(b[r+1]>0) {
    					if(b[r+1]-x>0) 	tc.add(r+1,-x);
    					else	tc.add(r+1,-b[r+1]);
    				}
    				b[l]+=x,b[r+1]-=x;
    			}
    			else {
    				cin>>l>>r;
    				cout<<tb.r_ask(1,l)+tc.r_ask(l+1,r)<<endl;
    			}
    		}
    		rep(i,1,n+5) tb.sum[i]=0,tc.sum[i]=0;
    	}
    	return 0;
    }

J. Time Limit

[2018-2019 ACM-ICPC, China Multi-Provincial Collegiate Programming Contest][2018-2019 ACM-ICPC_ China Multi-Provincial Collegiate Programming Contest]

A. Maximum Element In A Stack

#include<bits/stdc++.h>
    #define il inline
    #define pb push_back
    #define fi first
    #define se second
    #define ms(_data,v) memset(_data,v,sizeof(_data))
    #define sc(n) scanf("%d",&n)
    #define SC(n,m) scanf("%d %d",&n,&m)
    #define SZ(a) int((a).size())
    #define rep(i,a,b) for(int i=a;i<=b;++i)
    #define drep(i,a,b)    for(int i=a;i>=b;--i)
    using namespace std;
    typedef long long ll;
    int n,p,q,m;
    unsigned int SA,SB,SC;
    stack<long long>s;
    void PUSH(long long x){
        if(s.empty())s.push(x);
        else s.push(max(x,s.top()));
    }
    void POP(){
        if(!s.empty())
        s.pop();
    }
    unsigned int rng61(){
        SA ^= SA << 16;
        SA ^= SA >> 5;
        SA ^= SA << 1;
        unsigned int t = SA;
        SA = SB;
        SB = SC;
        SC ^= t ^ SA;
        return SC;
    }
    int main(){
        int T;
        scanf("%d",&T);
        for(int t = 1;t <= T;t++){
            while(!s.empty())s.pop();
            long long ans = 0;
            scanf("%d%d%d%d%u%u%u",&n,&p,&q,&m,&SA,&SB,&SC);
            for(int i = 1;i <= n;i++){
                if(rng61() % (p + q) < p) PUSH(rng61() % m + 1);
                else POP();
                if(!s.empty()) ans^=(i*s.top());
            }
            printf("Case #%d: %lld\n",t,ans);
        }
        return 0;
    }

F.Moving On

#include<bits/stdc++.h>
    #define il inline
    #define pb push_back
    #define fi first
    #define se second
    #define ms(_data,v) memset(_data,v,sizeof(_data))
    #define sc(n) scanf("%d",&n)
    #define SC(n,m) scanf("%d %d",&n,&m)
    #define SZ(a) int((a).size())
    #define rep(i,a,b) for(int i=a;i<=b;++i)
    #define drep(i,a,b)    for(int i=a;i>=b;--i)
    using namespace std;
    typedef long long ll;
    const ll inf=0x3f3f3f3f;
    const double PI=acos(-1.0);
    const double eps=1e-9;
    const int maxn=205;
    int T,dis[maxn][maxn],ans[20005],n,q;
    struct node {
        int id,w;
    } a[maxn];
    struct Qu {
        int id,u,v,w;
    } qu[20005];
    bool Qcmp(Qu x,Qu y)    {
        return x.w<y.w;
    }
    bool cmp(node x,node y)    {
        return x.w<y.w;
    }
    int main() {
        std::ios::sync_with_stdio(0);
        sc(T);
        for(int TT=1; TT<=T; ++TT) {
            SC(n,q);
            rep(i,1,n)    sc(a[i].w),a[i].id=i;
            sort(a+1,a+1+n,cmp);
            rep(i,1,n)    rep(j,1,n)    sc(dis[i][j]);
            rep(i,1,q) {
                sc(qu[i].u),sc(qu[i].v),sc(qu[i].w),qu[i].id=i;
            }
            sort(qu+1,qu+q+1,Qcmp);
            int cnt=1;
            for(int k=1;k<=q;++k){
                while(cnt<=n && a[cnt].w<=qu[k].w){
                    for(int i=1;i<=n;++i){
                        for(int j=1;j<=n;++j){
                            dis[i][j]=min(dis[i][j],dis[i][a[cnt].id]+dis[a[cnt].id][j]);
                        }
                    }
                    cnt++;
                }
                ans[qu[k].id]=dis[qu[k].u][qu[k].v];
            } 
            printf("Case #%d:\n",TT);
            rep(i,1,q)    printf("%d\n",ans[i]);
        }
        return 0;
    }

转载于:https://www.cnblogs.com/hxn-tj-cy/p/10952207.html

[The 13th Chinese Northeast Collegiate Programming Contest]: http://codeforces.com/gym/102220
[2018-2019 ACM-ICPC_ China Multi-Provincial Collegiate Programming Contest]: http://codeforces.com/gym/102222