2012天津网络赛赛后【缺CDH】

A Faulty Odometer (HDU 4278)

k*10^t中合法个数为(k-(k>3)-(k>8)*i^t，逐位计算

#include<iostream>
using namespace std;
int main()
{
    string s;
    while(cin>>s,s!="0")
    {
        int ans=0;
        for(int i=0;s[i];i++) ans=ans*8+s[i]-48-(s[i]>51)-(s[i]>56);
        cout<<s<<": "<<ans<<endl;
    }
    return 0;
}

B Number (HDU 4279)

打表找规律

 #include<iostream>
 using namespace std;
 int gcd(int a,int b){return b?gcd(b,a%b):a;}
 int cal(int x)
 {
     int ans=0;
     for(int i=1;i<=x;i++) if(x%i&&gcd(i,x)>1) ans++;
     return ans&1;
 }
 int main()
 {
     for(int i=1,tot=0;i<=100;i++) tot+=cal(i),cout<<i<<' '<<tot<<endl;
 }

n<4为0，n>=4 时偶数+1奇数+0（n不为平方数），n为平方数时相反

 #include<cmath>
 #include<iostream>
 using namespace std;
 typedef long long ll;
 ll cal(ll x)
 {
     if(x<4) return 0;
     ll tmp=(ll)sqrt(x+0.5);
     return tmp%2?x/2-1:x/2-2;
 }
 int main()
 {
     ll t,a,b;
     for(cin>>t;t;t--)
     {
         cin>>a>>b;
         cout<<cal(b)-cal(a-1)<<endl;
     }
     return 0;
 }

C Island Transport (HDU 4280)

D Judges’ response (HDU 4281)

E A very hard mathematic problem (HDU 4282)

z等于2时为(x+y)^2==k，直接计算，其它时候枚举z与y，二分x求解。

#include<cmath>
#include<iostream>
using namespace std;
typedef long long ll;
ll pow(ll a,int n)
{
    ll ans=1;
    while(n)
    {
        if(n&1) ans=ans*a;
        a=a*a;n>>=1;
    }
    return ans;
}
ll cal(ll x,ll y,ll z){return pow(x,z)+pow(y,z)+x*y*z;}
int main()
{
    ll k;
    while(cin>>k&&k)
    {
        ll tmp=sqrt(k*1.0)-1,ans=0;
        while(tmp*tmp<k) tmp++;
        if(tmp*tmp==k) ans=(tmp-1)/2;
        for(ll z=3;z<32;z++) for(ll y=2;cal(1,y,z)<=k;y++)
        {
            ll low=1,up=y,x=0;
            while(low<=up)
            {
                ll mid=(low+up)/2;
                if(cal(mid,y,z)<k) low=mid+1;
                else up=mid-1,x=mid;
            }
            if(cal(x,y,z)==k) ans++;
        }
        cout<<ans<<endl;
    }
    return 0;
}

F You Are the One (HDU 4283)

对于a[l],a[l+1],a[l+2],……,a[r-1],a[r]，利用栈将(l,r)区间顺序变成(l,l+i)，i，(l+i+1,r)三部分计算。

即dfs(l,r)=min{dfs(l,l+i)+dfs(l+i+1,r)+cost}，cost为i和(l+i+1,r)两部分将起始下标调整为0的代价。

#include<cstdio>
 
const int N=101;
int t,n,a[N],sum[N],dp[N][N];
int dfs(int l,int r)
{
    if(r<l) return 0;
    if(dp[l][r]!=0x3f3f3f3f) return dp[l][r];
    for(int i=0;i<=r-l;i++)
    {
       int tmp=dfs(l+1,l+i)+dfs(l+i+1,r)+(sum[r]-sum[l+i])*(i+1)+a[l]*i;
       if(tmp<dp[l][r]) dp[l][r]=tmp;
    }
    return dp[l][r];
}
int main()
{
    scanf("%d",&t);
    for(int cas=1;cas<=t;cas++)
    {
        scanf("%d",&n);
        for(int i=1;i<=n;i++) for(int j=i;j<=n;j++) dp[i][j]=0x3f3f3f3f;
        for(int i=1;i<=n;i++) scanf("%d",a+i),sum[i]=a[i]+sum[i-1];
        printf("Case #%d: %d\n",cas,dfs(1,n));
    }
    return 0;
}

G Travel (HDU 4284)

状态压缩DP。(DP什么的最讨厌了 2012天津市网络赛赛后【缺CDH】）

dp[st][k] 从起点出现能够通过k这个点转移到达状态st所需要消耗的最小代价。即dp[mask^st][w]状态可以消耗的最大代价为monkey-dp[st][k]-dis(k,w)。

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N=111,H=15,inf=0x3f3f3f3f;

int t,n,m,mon,h;
int g[N][N],dp[1<<H][H];
int id[H],c[H],d[H];

int main()
{
    //freopen("in","r",stdin);
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d%d",&n,&m,&mon);
        for(int i=0;i<=n;i++) for(int j=0;j<=n;j++) g[i][j]=i==j?0:inf;
        int x,y,z;
        while(m--) scanf("%d%d%d",&x,&y,&z),g[x][y]=g[y][x]=min(g[x][y],z);
        scanf("%d",&h);
        for(int i=0;i<h;i++) scanf("%d%d%d",id+i,c+i,d+i);
        for(int k=1;k<=n;k++) for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) g[i][j]=min(g[i][k]+g[k][j],g[i][j]);
        memset(dp,63,sizeof(dp));
        for(int i=0;i<h;i++) if(mon>=g[1][id[i]]+d[i]) dp[1<<i][i]=g[1][id[i]]+d[i]-c[i];
        for(int i=1;i<1<<h;i++) for(int j=0;j<h;j++) if(dp[i][j]!=inf) for(int k=0; k<h; k++)
        {
            if(j==k||i&1<<k) continue;
            int lim=dp[i][j]+g[id[j]][id[k]]+d[k];
            if(mon>=lim&&dp[1<<k|i][k]>lim-c[k])  dp[1<<k|i][k]=lim-c[k];
        }
        bool fg=0;
        for(int i=0;i<h;i++) if(dp[(1<<h)-1][i]+g[id[i]][1]<=mon) fg=1;
        puts(fg?"YES":"NO");
    }
    return 0;
}

H circuits (HDU 4285)

I Data Handler (HDU 4286)

2012天津市网络赛赛后【缺CDH】 Splay模板题............................................................................................................................................

class Splay
{
    int ccnt,ans[N];
    void out()
    {
        ccnt=0;
        dfs(root);
        for(int i=1;i<ccnt-1;i++) printf("%d%c",ans[i],i==ccnt-2?'\n':' ');
    }
    void dfs(node *t)
    {
        t->pushdown();
        if(t==null) return;
        dfs(t->ch[0]);
        ans[ccnt++]=t->key;
        dfs(t->ch[1]);
   }
}sp;

int main()
{
    //freopen("in.txt","r",stdin);
    int t,n;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        for(int i=1;i<=n;i++) scanf("%d",arr+i);
        sp.maketree(1,n);
        int l,r,m,x;
        scanf("%d%d%d",&l,&r,&m);
        while(m--)
        {
            char s[10];
            scanf("%s",s);
            if(s[0]=='M'&&s[4]=='L')
            {
                scanf("%s",s);
                if(s[0]=='L') l--;
                else r--;
            }
            else if(s[0]=='M'&&s[4]=='R')
            {
                scanf("%s",s);
                if(s[0]=='L') l++;
                else r++;
            }
            else if(s[0]=='I')
            {
                scanf("%s%d",s,&x);
                if(s[0]=='L') sp.insert(l-1,x),r++;
                else sp.insert(r,x),r++;
            }
            else if(s[0]=='D')
            {
                scanf("%s",s);
                if(s[0]=='L') sp.dele(l),r--;
                else sp.dele(r),r--;
            }
            else sp.reverse(l,r);
        }
        sp.out();
    }
    return 0;
}

J Intelligent IME (HDU 4287)

水题map<string,int>统计个数即可

#include<cstdio>
#include<string>
#include<map>
using namespace std;
char s[5555][10],ss[10];
int sw[]={2,2,2,3,3,3,4,4,4,5,5,5,6,6,6,7,7,7,7,8,8,8,9,9,9,9};
int main()
{
    int t,n,m;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&n,&m);
        map<string,int>mm;
        for(int i=0;i<n;i++) scanf("%s",s[i]);
        for(int i=0;i<m;i++)
        {
            scanf("%s",ss);
            for(int i=0;ss[i];i++) ss[i]=sw[ss[i]-97]+48;
            mm[ss]++;
        }
        for(int i=0;i<n;i++) printf("%d\n",mm[s[i]]);
    }
    return 0;
}

2012天津市网络赛赛后【缺CDH】