http://acm.hust.edu.cn:8080/judge/contest/view.action?cid=9593#overview
A题
模拟
#include <iostream>
using namespace std;
int gcd(int a,int b)
{
if (a<b) return gcd(b,a);
if (b==0) return a;
return gcd(b,a%b);
}
int main()
{
int l,r,n;
cin>>l>>r>>n;
//if (l>n) cout<<1<<endl;else
while (1)
{
n-=gcd(l,n);
if (n<0) {cout<<1<<endl;break;}else
n-=gcd(r,n);
if (n<0) {cout<<0<<endl;break;}
}
//while (1);
return 0;
}
C题
字符串处理
#include <iostream>
#include <cstdio>
using namespace std;
int main()
{
char s[1005];
cin>>s;
int i=0;
while (s[i])
{
if (!(s[i]=='a' || s[i]=='e' || s[i]=='i' || s[i]=='o' || s[i]=='u'
|| s[i]=='A' || s[i]=='E' || s[i]=='I' || s[i]=='O' ||s[i]=='U'
|| s[i]=='y' || s[i]=='Y') )
{
cout<<".";
if (s[i]<='Z')
printf("%c",s[i]-'A'+'a');else
printf("%c",s[i]);
}
i++;
}
cout<<endl;
//while (1);
return 0;
}
D题
模拟
#include <iostream>
#include <cstdio>
using namespace std;
int main()
{
int i,j;
int n;
cin>>n;
int p=0,q=n;
for (i=0;i<=n;i++)
{
q=i;
for (j=n;j>=0;j--)
{
if (j>q) printf(" ");else
if (q==j && i==0) printf("0");else
printf("%d ",q-j);
}
for (j=1;j<q;j++)
{
// if (j>q) printf(" ");else
printf("%d ",q-j);
}
if (i!=0)
printf("0");
// if (n>q) printf(" ");else
// if (n==q) printf("%d",0);
printf("\n");
}
for (i=n-1;i>=0;i--)
{
q=i;
for (j=n;j>=0;j--)
{
if (j>q) printf(" ");else
if (q==j && i==0) printf("0");else
printf("%d ",q-j);
}
for (j=1;j<q;j++)
{
// if (j>q) printf(" ");else
printf("%d ",q-j);
}
// if (n>q) printf(" ");else
if (i!=0) printf("0");
if (n==q) printf("%d",0);
printf("\n");
// return 0;
}
// while (1);
return 0;
}
E题
从0枚举到9,做10次sort
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define maxn 100000
using namespace std;
struct Node
{
int val,pos,vv;
};
Node node[maxn];
int ans[10];
int c[10][maxn];
int vc;
char str1[10][maxn];
bool cmp(Node x,Node y)
{
if (x.val!=y.val)
return x.val<y.val;
if (x.vv<vc)
{
if (y.vv>vc) return 0;else
return x.pos>y.pos;
} else
{
if (y.vv<vc) return 1;else
return x.pos<y.pos;
}
}
int main()
{
int n,m,j,k;
char str[maxn];
cin>>n>>m;
cin>>str;
int i=0;
while (str[i])
{
node[i].val=str[i]-48;
node[i].vv=node[i].val;
node[i].pos=i;
i++;
}
for (i=0;i<=9;i++)
{
vc=i;
for (j=0;j<n;j++)
node[j].val=abs(node[j].vv-i);
sort(node,node+n,cmp);
int cnt=0;
int pos=0;
ans[i]=0;
for (k=0;k<m;k++)
{
//while (node[cnt].val==0) cnt++;
ans[i]+=abs(node[cnt].val);
c[i][++c[i][0]]=node[cnt].pos;
cnt++;
}
for (int p=0;p<n;p++)
str1[i][p]=str[p];
for (int p=1;p<=c[i][0];p++)
str1[i][c[i][p]]=i+48;
}
int mina=ans[0];
int ansi=0;
for (int i=1;i<=9;i++)
if (ans[i]<mina)
{
mina=ans[i];
ansi=i;
} else
if (ans[i]==mina)
{
if (strcmp(str1[i],str1[ansi])<0)
ansi=i;
}
// printf("%d\n",ansi);
cout<<mina<<endl;
/*for (i=1;i<=c[ansi][0];i++)
str[c[ansi][i]]=ansi+48;*/
printf("%s",str1[ansi]);
//while (1);
return 0;
}
/*
6 5
898196
*/
F题
DP
#include <iostream>
#include <cstdio>
#define MAX(a,b) ((a)>(b)?(a):(b))
#define M 100000000
using namespace std;
int f[205][105][15],g[205][105][15];
int main()
{
int n1,n2,k1,k2,n;
cin>>n1>>n2>>k1>>k2;
n=n1+n2;
f[0][0][0]=1;
g[0][0][0]=1;
f[1][1][1]=1;
g[1][0][1]=1;
for (int i=2;i<=n;i++)
{
int maxj,minj;
if (i<=n1) maxj=i;else maxj=n1;
if (i-n2>0) minj=i-n2;else minj=0;
for (int j=minj;j<=maxj;j++)
{
int maxp;
if (j<k1) maxp=j;else maxp=k1;
for (int pp=1;pp<=k2;pp++)
f[i][j][0]=(f[i][j][0]+g[i-1][j][pp] )%M;
for (int pp=1;pp<=k2;pp++)
f[i][j][1]=(f[i][j][1]+g[i-1][j-1][pp] )%M;
for (int p1=2;p1<=maxp;p1++)
if (j>0)
f[i][j][p1]=f[i-1][j-1][p1-1] %M;
if (i-j<k2) maxp=i-j;else maxp=k2;
for (int pp=1;pp<=k1;pp++)
g[i][j][0]=(g[i][j][0]+f[i-1][j-1][pp] )%M;
for (int pp=1;pp<=k1;pp++)
g[i][j][1]=(g[i][j][1]+f[i-1][j][pp] )%M;
for (int p1=2;p1<=maxp;p1++)
// if (j>0)
g[i][j][p1]=g[i-1][j][p1-1] %M;
}
}
int ans=0;
for (int i=1;i<=k1;i++)
ans=(ans+f[n][n1][i]) %M;
for (int i=1;i<=k2;i++)
ans=(ans+g[n][n1][i]) %M;
printf("%d\n",ans);
// while (1);
return 0;
}
/*
f[i][j][k]=
f[i-1][j-1][k]
f[i-1][
f[i][0]=max ( g[i][1..k2-1])
f[i][j]=f[i-1][j-1]
g[i][j]=g[i-1
*/
posted @
2012-07-22 00:36 aZL@hust 阅读(199) |
评论 (0) |
编辑 收藏
就是这样...
posted @
2012-07-22 00:15 aZL@hust 阅读(132) |
评论 (0) |
编辑 收藏