Codeforces Round #261 (Div. 2) - c++编程基础

TOP

Codeforces Round #261 (Div. 2)

2015-07-20 17:53:03 来源: 作者: 【大中小】浏览:1次

A. Pashmak and Garden

题意：已知两个顶点的坐标，如果能推断出另外两个顶点则输出（special judge）。如果这两个顶点不是构成正方形的两个顶点，

则输出-1。

水题，1A，不多说。

#include
  
   
#include
   
     #include
    
      #include
     
       using namespace std; int main() { int x1,x2,y1,y2,flag,x3,y3,x4,y4,l; while(scanf("%d%d%d%d",&x1,&y1,&x2,&y2)!=EOF) { int t1 = fabs(x2-x1); int t2 = fabs(y2-y1); flag = 0; if(!t1) { l = t2; x3 = x4 = x1+t2; y3 = y1; y4 = y2; } else if(!t2) { l = t1; y3 = y4 = y1+t1; x3 = x1; x4 = x2; } else { if(t1!=t2) flag = 1; else { l = t1; x3 = x1; y3 = y2; x4 = x2; y4 = y1; } } if(flag) printf("-1\n"); else printf("%d %d %d %d\n",x3,y3,x4,y4); } return 0; }

B. Pashmak and Flowers

题意：

有n朵花，每朵有个beauty值。问能找到的beauty值的最大差异是多少?选择具有最大差异的两朵花有几种方案?

输出这两个值。

只要统计最大值和最小值，以及最大值与最小值的个数cnt1、cnt2即可，方案数为cnt1*cnt2。

特判：如果最大差异值为0，即最大值等于最小值时，方案数为n*(n-1)/2。

#include
  
   
#include
   
     #include
    
      #define maxn 200010 #define INF 0x3f3f3f3f using namespace std; typedef long long ll; int f[maxn]; int main() { int n,maxv,minv; ll cnt1,cnt2,ans; scanf("%d",&n); minv = INF,maxv = -INF; for(int i=1;i<=n;i++) { scanf("%d",&f[i]); if(f[i]>maxv) maxv = f[i]; if(f[i]
     
      
 
      
 
       
      C. Pashmak and Buses
  
      题意： 
      有n个学生，k辆bus，d天。要安排n个学生d天乘坐的bus，使得没有两个学生的车d天都是相同的。 
      
  
      算法： 
      首先，每天每个学生有k种乘坐方案（1-k车)，那么d天总共能有k^d种不同的乘坐方案。 
      如果n>k^d，则必有两个学生是行程安排相同的。（容斥原理）==>此种情况输出-1. 
      由于k很大，如果一直乘方或者快速幂即使用long long也会溢出，但是如果只要判断其与n的大小， 
      而n最大为1000，则设一个>1000且在int范围内的INF即可，一旦大于INF，则break。 
      
  
      其次，麻烦的是要输出n个学生的每天的车的安排情况。 
      开始用全排列next_permutation自己想了一种方案，改了很久，写了快200行，但是有问题。后来看了别人的写法，顿感无比精妙! 
      由于n个学生必定存在不同的方案，此时利用 n%k+1和n/=k的序列一定会不同来构造ans[i][j](第i天第j个 
      学生乘坐几号车) 
      
  
      
      #include
       
        
#include
        
          #include
         
           #define INF 10000000 #define maxn 1010 using namespace std; int ans[maxn][maxn]; int main() { int n,k,d; while(scanf("%d%d%d",&n,&k,&d)!=EOF) { int res = 1; for(int i=1;i<=d;i++) { res = res*k; if(res>INF) { res = INF; break; } } if(res
          
            
           
  D. Pashmak and Parmida's problem 
           题意： 
           定义f(l,r,x)为i属于[l，r]区间，a[i]=x的个数。 
           求满足f（1，i,a[i])>f(j,n,a[j] )且i
            
             n?≤?10
             ⁶
             
           
  
           算法： 
           统计a[i]左边与它相等的个数和a[j]右边与它相等的值的个数都要扫一遍。 
           因为要计数，暴力方法不是费时（两种循环）就是费内存无法处理（a[i]最大有10^9，数组开不下）。 
           用map神器来计数O(∩_∩)O哈！ 
           
  
           然后用树状数组来存ri[i]的个数。 
           从1-n扫描，每次先把当前的ri[i]值更新即个数-1.保证下标为j>i.即此时j=i+1.....i+n 
           然后找i+1的ri值中比le[i]值小的个数。 
           
  
           
           #include
            
             
#include
             
               #include
              
                #include
                #define maxn 1000010 using namespace std; typedef long long ll; map
                
                  s; int le[maxn],ri[maxn],c[maxn],n,a[maxn]; int lowbit(int x) { return x&(-x); } int que(int pos) { int sum = 0; while(pos>0) { sum+=c[pos]; pos -= lowbit(pos); } return sum; } void update(int pos,int v) { while(pos<=n) { c[pos]+=v; pos += lowbit(pos); } } int main() { ll ans; while(scanf("%d",&n)!=EOF) { s.clear(); memset(le,0,sizeof(le)); memset(ri,0,sizeof(ri)); for(int i=1;i<=n;i++) scanf("%d",&a[i]); for(int i=1;i<=n;i++) { s[a[i]]++; le[i] = s[a[i]]; } s.clear(); for(int j=n;j>=1;j--) { s[a[j]]++; ri[j] = s[a[j]]; } for(int i=n;i>=1;i--) update(ri[i],1); ans = 0; for(int i=1;i<=n;i++) { update(ri[i],-1); ans+=que(le[i]-1); } printf("%I64d\n",ans); } return 0; } 
                
              
             
            
           
 E. Pashmak and Graph
            
           题意：n个点m条边的有向图，求一条路径，使得路径上的边权值严格单调递增且路径上的边数最多。 
           输出最大边数。 
           
  
           算法： 
           首先按边权从小到大排序，没有相等的边时，可以直接更新dp[e[i].to] = max(dp[e[i].fr]+1,dp[e[i].to]。 
           但是如果有相等的边，这样一步一步的更新会把数量相加即把相等的边算在一条路径上的边数上。 
           所以我们要设一个中间数组f，让所有边权相等的边先从dp[e[i].fr]那里转移再一起更新。 
           
  
           
           #include
            
             
#include
             
               #include
              
                #include
               
                 #define maxn 300010 using namespace std; int dp[maxn],n,m,f[maxn]; struct node { int fr,to,v; }e[maxn]; bool cmp(node x,node y) { return x.v


【大中小】【打印】【繁体】【投稿】【收藏】【推荐】【举报】【评论】【关闭】【返回顶部】
分享到:
上一篇：List对象排序通用方法	下一篇：C++ 我想这样用（五）

帐　　号:

密码: (新用户注册)

验证码:

表　　情:

内　　容: