codeforces #204(div2)

a.题意：给n个数，其中只有0和5，组成一个最大的可以被90整除的数

分析:，没有0肯定不能被90整除，那么只要找到若干个5组成的数，与9的余数的循环节就好了，9的倍数个5可以被9整除，那么输出(b/9)*9个5+若干个0就好了

如果没有0，组成的数不可能被90整除，输出-1

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int maxn=1e5+5;
 4 typedef long long ll;
 5 
 6 int main(){
 7     
 8     //freopen("in","r",stdin);
 9     
10     int res,n,a,b;
11     cin>>n;
12     a=b=0;
13         
14     for(int i=0;i<n;i++){
15         cin>>res;
16         if(res)b++;
17         else a++;
18     }
19     b/=9;
20     if(b&&a){
21         for(int i=0;i<b;i++)
22             for(int j=0;j<9;j++)
23                 putchar('5');
24         while(a--)putchar('0');
25         puts("");
26     }
27     else if(a)puts("0");
28     else puts("-1");
29     return 0;
30 }

View Code

b.题意：给一个n个数的序列，如果一个数x的所有下标是一个等差序列，那么输出他

分析：map套vector，然后每一个vector排序，然后判断下标是否是等差序列就行了

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int maxn=1e5+5;
 4 typedef long long ll;
 5 
 6 int a[maxn],b[maxn];
 7 
 8 map<int,vector<int> > v;
 9 map<int,vector<int> >::iterator it;
10 
11 queue<pair<int,int> > q;
12 
13 int main(){
14     
15     int n;
16     cin>>n;
17     
18     for(int i=0;i<n;i++){
19         cin>>a[i];
20         v[a[i]].push_back(i);
21     }
22     
23     
24     for(it=v.begin();it!=v.end();it++){
25         vector<int> x=it->second;
26         if(x.size()==1)q.push(make_pair(it->first,0));
27         else{
28             int res=x[1]-x[0];
29             for(int i=2;i<x.size();i++)
30                 if(x[i]-x[i-1]!=res){
31                     res=-1;break;
32                 }
33             if(res!=-1)q.push(make_pair(it->first,res));
34         }
35     }
36     
37     cout<<q.size()<<endl;
38     
39     while(!q.empty()){
40         pair<int,int> pr=q.front();q.pop();
41         cout<<pr.first<<" "<<pr.second<<endl;
42     }
43     
44     return 0;
45 }

View Code

c.题意：给n*2个数，找到n个这样的数对，(ai,aj) ,前一个数向下取整，后一个数向下取整，输出修改后的序列和与原序列和的差的最小的绝对值

分析：假设res是若干个数都向下取整的数与原数的差的和的绝对值，假设res=a1+a2+...a2n,如果一个数要改变为向上取整的话，res=fabs(res-1);

序列中存在一些数，比如1.000，向上取整和向下取整是一样的，所以只要枚举剩下的数中有多少向上取整，满足题目要求中的n个向上取整，n个向下取整，然后计算ans就好了

范围是[max(0,n-cnt),min(n,2*n-cnt)],

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const double esp=1e-9;
 4 int main(){
 5     
 6     double res=0,x;
 7     int n,cnt=0;
 8     cin>>n;
 9     
10     for(int i=0;i<n*2;i++){
11         cin>>x;
12         if((x-floor(x))<esp)++cnt;
13         res+=x-floor(x);
14     }
15     
16     //cnt个可以向上也可以向下
17     //然后就是凑够n个向上的
18     //现在存的都是向下取整，改变为向上取整的话，
19     //-1就行了
20     
21     double ans=INT_MAX;
22     
23     for(int i=max(0,n-cnt);i<=min(n,2*n-cnt);i++)
24         ans=min(ans,fabs(res-i));
25     printf("%.3f
",ans);
26     
27     return 0;
28 }

View Code

d.题意：给一个序列，如果序列中不存在逆序对就停止，每次操作你可以减少一个逆序对，在你操作之后，还会有一次概率操作，50%让你增加一个逆序对，50%减少一个逆序对

，输出期望的次数

分析：先统计逆序对数，假设逆序对数是2，可以手算出期望是4，是3，期望是5，发现规律 cnt*2-(cnt&1)