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求解。

）
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)

Splay模板题............................................................................................................................................
#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;}