天天看點
傳回

2014多校訓練九（HDU 4960 HDU 4961 HDU 4965 HDU 4968 HDU 4969 HDU 4970）

HDU 4960 Another OCD Patient

題意：給你一串數字  相鄰x個數字合并成一個數字（相加）有一定代價  問  最少花費多少使得串變成回文串

思路：

讀完題感覺像dp  資料範圍也像  就開始想怎麼表示狀态  最簡單的應該想到dp[i][j]表示i到j區間變成回文串的最小花費  狀态想好了想做法  考慮将串分成AAAABBBBBBBCCC三段  即所有A合成一個數字  C也是  而且A和C相等  那麼B串就變成了子問題  但是A和C是不是都要枚舉呢？  這個串所有元素都是正的  那麼也就是對于一種A隻能對應一種C  是以這個枚舉複雜度是O(n)的  而且每次做子問題都會至少去掉首尾2個元素  那麼複雜度也就是n^2級别

代碼：

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define N 5010
#define inf 2000000000
typedef __int64 LL;

int n,amt;
int cost[N],dp[N][N];
LL sum[N];

int dfs(int l,int r)
{
    if(l>=r) return 0;
    if(dp[l][r]!=inf) return dp[l][r];
    int i,j;
    LL suml,sumr;
    dp[l][r]=cost[r-l+1];
    for(i=l,j=r;i<j;)
    {
        suml=sum[i]-sum[l-1];
        sumr=sum[r]-sum[j-1];
        if(suml==sumr)
        {
            dp[l][r]=min(dp[l][r],dfs(i+1,j-1)+cost[i-l+1]+cost[r-j+1]);
            i++;
            j--;
        }
        else if(suml>sumr) j--;
        else i++;
    }
}

int main()
{
    int i,j;
    while(~scanf("%d",&n))
    {
        if(!n) break;
        for(i=1;i<=n;i++)
        {
            scanf("%I64d",&sum[i]);
            sum[i]+=sum[i-1];
        }
        for(i=1;i<=n;i++) scanf("%d",&cost[i]);
        for(i=1;i<=n;i++)
        {
            for(j=1;j<=n;j++) dp[i][j]=inf;
        }
        dfs(1,n);
        printf("%d\n",dp[1][n]);
    }
    return 0;
}

HDU 4961 Boring Sum

題意：略

思路：

隊友做的  他一眼就看出來了…- -b  膜拜豬神！  做法就是正反掃兩邊  對于每個數  維護它的所有約數  這樣b和c數組相當于已知了  最後掃一遍求和

代碼：

#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
using namespace std;
typedef __int64 ll;
const ll mod = 1000000009;
const double eps = 1e-9;
const double pi = acos(-1.0);
const int M=100005;
int n,m;
vector<int > F[M];

void init()
{
    int i,j;
    for(i=1;i<M;i++)
        for(j=i;j<M;j+=i)
            F[j].push_back(i);
}
int dpa[M],dpb[M];
int ansa[M],ansb[M];
int a[M];
int main()
{
    init();
    int i,j;
    int T,ca=0;
    while(~scanf("%d",&n))
    {
        memset(dpa,0,sizeof(dpa));
        memset(dpb,0,sizeof(dpb));
        if(!n)
            break;
        for(i=1;i<=n;i++)
            scanf("%d",&a[i]);
        for(i=1;i<=n;i++)
        {
            if(!dpa[a[i]])
                ansa[i]=i;
            else
                ansa[i]=dpa[a[i]];
            for(j=0;j<F[a[i]].size();j++)
            {
                int now=F[a[i]][j];
                dpa[now]=i;
            }
        }
        for(i=n;i>=1;i--)
        {
            if(!dpb[a[i]])
                ansb[i]=i;
            else
                ansb[i]=dpb[a[i]];
            for(j=0;j<F[a[i]].size();j++)
            {
                int now=F[a[i]][j];
                dpb[now]=i;
            }
        }
        ll ans=0;
        for(i=1;i<=n;i++)
        {
            int x,y;
            x=a[ansa[i]];y=a[ansb[i]];
            ans=ans+(ll)x*y;
        }
        printf("%I64d\n",ans);
    }
    return 0;
}

HDU 4965 Fast Matrix Calculation

題意：給你矩陣A和B  分别是1000*6和6*1000的  求 C=AB  X=C^(n^2)  sum(C[i][j]%6)

思路：

利用矩陣相乘的結合律  ABABAB...ABAB = A (BA)(BA)... (BA) B 所有的BA可以處理成6*6矩陣快速幂搞  線性代數内容

代碼：

#include <iostream>
#include <string.h>
#include <stdio.h>
using namespace std;

int N;
int MOD=6;

typedef struct
{
    int m[100][100];
}Matrix;
void clear(Matrix &a)
{
    memset(a.m,0,sizeof(a.m));
}

Matrix E;

void danweiE()//機關矩陣！！！！
{
    int i,j;
    for(i=0;i<100;i++)
    for(j=0;j<100;j++)
        if(i==j)E.m[i][j]=1;
        else E.m[i][j]=0;
}

Matrix Add(Matrix a,Matrix b)  //矩陣加法(%MOD)  
{  
    int i,j;
    Matrix c;  
    for (i=0; i<N; i++)  
      for (j=0; j<N; j++)  
      {  
          c.m[i][j]=a.m[i][j]+b.m[i][j];  
          c.m[i][j]%=MOD;  
      }  
    return c;  
}

Matrix multi(Matrix a,Matrix b)//矩陣相乘！！！
{
    Matrix c;
    int i,j,k;
    clear(c);
    for(i=0;i<N;i++)
        for(j=0;j<N;j++)
            if(a.m[i][j])
            for(k=0;k<N;k++)
        if(b.m[j][k])
                c.m[i][k]=(c.m[i][k]+a.m[i][j]*b.m[j][k])%MOD;
    return c;
}

Matrix matrix_mod(Matrix a,int k)//矩陣快速幂！！！
{
    danweiE();
    Matrix ans=E,p=a;  
    while(k)
    {
        if(k&1)
        {
            ans=multi(ans,p);
            k--;
        }
        k>>=1;
        p=multi(p,p);
    }
    return ans;
}
int x[1010][1010],y[1010][1010],tmp[1010][1010];
int n,k;
Matrix a,ans;
void debug()
{
    int i,j;
    for(i=0;i<n;i++)
        for(j=0;j<k;j++)
            printf("%d%s",x[i][j],j==k-1?"\n":" ");
    for(i=0;i<k;i++)
        for(j=0;j<n;j++)
            printf("%d%s",y[i][j],j==n-1?"\n":" ");    
    for(i=0;i<k;i++)
        for(j=0;j<k;j++)
            printf("%d%s",a.m[i][j],j==k-1?"\n":" ");
    for(i=0;i<k;i++)
        for(j=0;j<k;j++)
            printf("%d%s",ans.m[i][j],j==k-1?"\n":" ");        
} 
int main()
{   
    int i,j,ii;
    while(scanf("%d%d",&n,&k))
    {
        if(!n&&!k)
            break;
        N=k;
        for(i=0;i<n;i++)
        for(j=0;j<k;j++)
            scanf("%d",&x[i][j]),x[i][j]%=6;
        for(i=0;i<k;i++)
        for(j=0;j<n;j++)
            scanf("%d",&y[i][j]),y[i][j]%=6;
        clear(a);
        for(i=0;i<k;i++)
        for(j=0;j<k;j++)
        {
            for(ii=0;ii<n;ii++)
            {
                a.m[i][j]+=y[i][ii]*x[ii][j];
            }
            a.m[i][j]%=6;
        }
        ans=matrix_mod(a,n*n-1); //算矩陣A^n次！！！！ 
        
          //debug();   
        for(i=0;i<n;i++)
        for(j=0;j<k;j++)
        {
            tmp[i][j]=0;
            for(ii=0;ii<k;ii++)
            {
                tmp[i][j]+=x[i][ii]*ans.m[ii][j];
            }
            tmp[i][j]%=6;
        }
        int ans=0;
        for(i=0;i<n;i++)
        for(j=0;j<n;j++)
        {
            int tt=0;
            for(ii=0;ii<k;ii++)
            {
                tt+=tmp[i][ii]*y[ii][j];
            }
            ans+=(tt%6);
        }
        printf("%d\n",ans);
    }
    return 0;
}

HDU 4968 Improving the GPA

題意：告訴你平均分和科目數  問  你能得到的最大績點和最小績點是多少

思路：

作為經常被卡績點的人  我表示這題想法來的很快- -b

對于最小績點  那麼一定是所有科目都先加到69  然後如果總分還有剩餘  就争取把課堆到100  為什麼呢  因為69和100最浪費分 - -b

對于最大績點  一定是所有的都從60開始  然後向85堆  為什麼呢  因為反正長5分就是0.5績點  哪科長都一樣  長到85就沒有繼續的意義了

代碼：

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define N 100010
typedef __int64 LL;

int t,n,amt;
double mx,mn;

double cal(int f)
{
    if(f>=85) return 2;
    if(f>=80) return 1.5;
    if(f>=75) return 1;
    if(f>=70) return 0.5;
    return 0;
}

int main()
{
    int i,j;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&amt,&n);
        amt*=n;
        i=amt-n*69;
        mn=n*2;
        while(i>0)
        {
            if(i>=31)
            {
                mn+=2;
                i-=31;
            }
            else
            {
                mn+=cal(i+69);
                i=0;
            }
        }
        i=amt-n*60;
        mx=n*2;
        j=0;
        while(i>0&&j<n)
        {
            if(i>=25)
            {
                mx+=2;
                i-=25;
            }
            else
            {
                mx+=cal(i+60);
                i=0;
            }
            j++;
        }
        printf("%.4f %.4f\n",mn/n,mx/n);
    }
    return 0;
}

HDU 4969 Just a Joke

題意：隊友看的- -b  大緻就是問從圓心起跑的點在時刻保持自己與圓心與圓周上的點共線的情況下能不能在D距離内追到圓周上的點

思路：完全數學題- -b  推出來特别好寫…  也不卡精度…

代碼：

#include <iostream>
#include <string.h>
#include <stdio.h>
#include <math.h>
using namespace std;

int N;
int MOD=6;
double v1,v2,r,d,k,a;
int main()
{
    int i,j,ii;
    int T;
    scanf("%d",&T);
    while(T--)
    {
        int aa,bb,cc,dd;
        scanf("%d%d%d%d",&aa,&bb,&cc,&dd);
        v1=1.0*aa;v2=1.0*bb;r=1.0*cc;d=1.0*dd;
        a=r*v2/v1;
        r=asin(r/a);
        double ans=a*r;
        if(ans>d)
            printf("Why give up treatment\n");
        else
            printf("Wake up to code\n");
    }
    return 0;
}

HDU 4970 Killing Monsters

題意：又是塔防遊戲…  每個塔有個攻擊範圍有個攻擊力  每個怪有個起跑位置有個血量  問幾隻怪能跑過去

思路：

從後到前掃一遍計算從x點開始到最後一共受多少傷害  （别開腦洞用什麼樹狀數組…就直接掃一遍…我很不了解為啥有人上來就資料結構…）  最後對每個怪判斷一下即可

代碼：

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define N 100010
typedef __int64 LL;

int n,m,ans;
LL sum[N],add[N];

int main()
{
    int i,j,l,r,d;
    LL ad;
    while(~scanf("%d",&n))
    {
        if(!n) break;
        memset(sum,0,sizeof(sum));
        memset(add,0,sizeof(add));
        scanf("%d",&m);
        while(m--)
        {
            scanf("%d%d%d",&l,&r,&d);
            add[r]+=d;
            add[l-1]-=d;
        }
        ad=0;
        for(i=n;i>=1;i--)
        {
            ad+=add[i];
            sum[i]=sum[i+1]+ad;
        }
        //for(i=1;i<=n;i++) printf("%I64d  ",sum[i]);
        ans=0;
        scanf("%d",&m);
        while(m--)
        {
            scanf("%I64d%d",&ad,&d);
            if(sum[d]<ad) ans++;
        }
        printf("%d\n",ans);
    }
    return 0;
}
HDU dp 數論 數學 想法
上一篇: [LeetCode]312. 戳氣球
下一篇: python繪制餅狀圖 标題_[Python Study Notes]餅狀圖繪制

繼續閱讀