多校2

IT/互联网 / 编程语言 养生小编 来源:互联网 153浏览 0评论

A HDU 5734

t 组样例

n  n个数字 w[i]    b 是1或者 -1

求 min   1~n  sum(w[i]-a*b)^2

展开  1~n sum(w[i]^2) + a*a*n- 2*a*(w[1]*b1+w[2]*b2 ...);

a>0  二次函数 a变量     最小  a= (w[1]*b1...)/n;

然后 求和  求一下gcd 就行  long long

技术分享技术分享
#include<stdio.h>#include<algorithm>#include<stdlib.h>#include<cstring>#include<string>#include<cmath>#include<vector>#include<queue>#include<map>#include<iterator>#include<stack>using namespace std;#define ll   __int64#define MAXN  100010#define inf  1000000000#define mod 1000000007int w[MAXN];ll gcd(ll a ,ll b){    return b?gcd(b,a%b):a;}int main(){    int t;    scanf("%d",&t);    while(t--)    {        int n;        scanf("%d",&n);        ll ans = 0;        ll a,sum;        sum=0;        for(int i=1;i<=n;i++)        {            scanf("%d",&w[i]);            ans = ans + w[i]*w[i];            sum= sum +abs(w[i]);        }        ans = ans *n;        ans = ans -sum*sum;        ll d= gcd(ans,(ll)n);        printf("%I64d/%I64dn",ans/d,n/d);    }    return 0;}
View Code

I HDU 5742

t 组样例 n 个位置  m个限制

 a b

w[a] =b;

求 w[1]+w[2]/sum;

贪心  前面尽量大 比前面小后面大就行 gcd

技术分享技术分享
#include<stdio.h>#include<algorithm>#include<stdlib.h>#include<cstring>#include<string>#include<cmath>#include<vector>#include<queue>#include<map>#include<iterator>#include<stack>using namespace std;#define ll   __int64#define MAXN  100010#define inf  1000000000#define mod 1000000007int z[MAXN];int gcd(int a,int b){    return b?gcd(b,a%b):a;}int main(){    int t;    scanf("%d",&t);    while(t--)    {        int n,m;        memset(z,0,sizeof(z));        scanf("%d%d",&n,&m);        for(int i=1;i<=m;i++)        {            int a,b;            scanf("%d%d",&a,&b);            z[a]=b;        }        if(z[1]==0)            z[1]=100;        if(z[2]==0)            z[2]=z[1];        int nex=0;        int j=3;        while(j<=n)        {            nex=0;            for(int k=j;k<=n;k++)                if(z[k]!=0)                {                    nex=k;                    break;                }            if(nex==0)            {                for(int k=j;k<=n;k++)                    z[k]=0;                break;            }            else            {                for(int k=j;k<nex;k++)                    z[k]=z[nex];            }            j=nex+1;        }        int sum=0;        for(int i=1;i<=n;i++)            sum=sum+z[i];        int a=z[1]+z[2];        int d=gcd(sum,a);        printf("%d/%dn",a/d,sum/d);    }    return 0;}
View Code

K HDU 5744

t 组样例

n n个数字

分别代表每个字母的个数

问 像分成的都是回文串的 集合中 最短的字符串的 最大长度   就是取集合中最短的   然后所有集合中最大的

就是要分的平均一点   奇数的个数显然是回文串的数目 那么怎么最大呢  平均点

每个偶数的长度都是可以分给别人的 奇数的可以变为1 然后剩下的长度用来分

得到的长度用来大家分

取小的就行了

技术分享技术分享
#include<stdio.h>#include<algorithm>#include<stdlib.h>#include<cstring>#include<string>#include<cmath>#include<vector>#include<queue>#include<map>#include<iterator>#include<stack>using namespace std;#define ll   __int64#define MAXN  100010#define inf  1000000000#define mod 1000000007int z[MAXN];int main(){    int t;    scanf("%d",&t);    while(t--)    {        int n;        scanf("%d",&n);        int cnt,sum;        sum=0;        cnt=0;        for(int i=1;i<=n;i++)        {            int a;            scanf("%d",&a);            if(a%2==1)            {                z[cnt++]=1;                sum=sum+a-1;            }            else                sum=sum+a;        }        if(cnt==0)        {            printf("%dn",sum);            continue;        }        int b=sum/(cnt*2);        for(int i=0;i<cnt;i++)            z[i]=z[i]+b*2;        sum=sum-b*cnt*2;        int j=0;        while(sum>0)        {            z[j]=z[j]+2;            sum=sum-2;            j++;        }        printf("%dn",z[j]);    }    return 0;}
View Code

 

多校2

原文:http://www.cnblogs.com/cherryMJY/p/6623303.html