这个题目先开始一直没有好的想法。
题目也是看了很久才看懂
师姐先开始的想法很好但是我没有去做。
最后兜了很大一个圈子还是回到了以前的想法
就是模拟的去建一个数然后给每个位置标号没上成一层就加1
然后再从树根上往下扫一遍。然后树根为1每个位置往下的时候加一
然后这个排序就可以了
最后这个题代码由敏哥完成了
1
#include<stdio.h>
2#include<algorithm>
3using namespace std;
4
5struct nn
6
{
7
int dp,m,mark;
8
}pt[10010];
9
10int len,t;
11char str[11000];
12
13void di(int deep)
14{
15 pt[t].dp = deep;
16 pt[t].m = str[len];
17 pt[t++].mark = t;
18 if(str[len] >= 'A' && str[len] <= 'Z')
19
{
20 len--;
21 di(deep+1);
22 di(deep+1);
23 return;
24
}
25 if(str[len] >= 'a' && str[len] <= 'z')
26 {
27 len--;
28 return;
29 }
30}
31
32int cmp(nn a, nn b)
33{
34 if(a.dp != b.dp)
35 return a.dp > b.dp;
36 else
37 return a.mark < b.mark;
38}
39
40int main()
41{
42 int n,i;
43 scanf("%d", &n);
44 while(n--)
45 {
46 scanf("%s",str);
47 len = strlen(str)-1;
48 t = 0;
49 di(0);
50 sort(pt,pt+t,cmp);
51 for(i = 0; i < t; i++)
52 printf("%c",pt[i].m);
53 printf("\n");
54 }
55 return 0;
56}
57
58
题目描述看了半天才看懂
就是找到四个**.**这样的数字但是最小是00.01
然后让这个四个数字的和等于四个数字的乘积
当时感觉暴力绝对超时就没写
后来别的题目写完了就没得写了
开始用暴力写这个当时别人已经用暴力把这个过了
然后开始写，先开始用实数来写的估计是因为精度问题一直不对
后来越写越郁闷
直接把程序全删除了。然后理清思路直接用整数来完成了一个就过了。
这个题可以先多枚举一些然后吧答案全都打出来
然后就可以知道第一个数第二个数。。。每个位置的数所能达到的最大值
然后以后搜索的时候只枚举到这个位置就好了
然后就过了
1#include<stdio.h>
2#include<math.h>
3int main()
4{
5 //freopen("asdas.txt","w",stdout);
6 int i,j,k,t;
7 for(i=1;i<160;i++)
8 for(j=i;j<1000;j++)
9 for(k=(2000-i-j)/2-1;k>=j;k--)
10 {
11 if(i*j*k<=1000000)break;
12 if( ((i+j+k)*1000000)%(i*j*k-1000000)==0 )
13 {
14 t=((i+j+k)*1000000)/(i*j*k-1000000);
15 if(t+i+j+k>2000)continue;
16 if(t<k)continue;
17 //printf("%d %d %d %d\n",i,j,k,t);
18 printf("%.2lf %.2lf %.2lf %.2lf\n",i/100.0,j/100.0,k/100.0,t/100.0);
19 }
20 }
21 return 0;
22}
23
24
25
这个题目是Ulm Local 2007比赛的。
今天我们组队做了5个小时Ulm Local 2007比赛
在比赛还有半小时AC了6个还差两个题目
一个是线段数的感觉没时间写了
另一个就是这个了。先开始一直想不出来很好的算法。
听后面一个全做完的队再说这个可以用鸽笼原理来证明还说这个题目只要找出连续的集合就可以了
然后听到之后仔细想了一下感觉有道理
当把所有从第一个开始的部分和对C的余数统计就可以发现
要么就是有一个人给的糖果直接就是C的倍数
要么会出现两个部分和对C取余后得到相同的值
这就说明相同这两个之间的部分和就是C的倍数
然后题目写起来就很简单了
写了没几分钟然后交了就A了
后来下来听那个队说他们这个想法居然是baidu出来的
然后小鄙视了一下他们。
不过想想我也是听力人家说以后才有了想法的啊
1#include<stdio.h>
2int data[110000];
3int mark[110000],n,c;
4int main()
5{
6 int i,a,b,sum;
7 while(scanf("%d%d",&c,&n),c){
8
9 for(i=0;i<n;i++){
10 mark[i]=0;
11 scanf("%d",&data[i]);
12 }
13 sum=0;
14 for (i=0;i<n;++i){
15 sum=(sum+data[i])%c;
16 if (sum==0){
17 a=1;
18 b=i+2;
19 break;
20 }
21 if (mark[sum]){
22 a=mark[sum]+1;
23 b=i+2;
24 break;
25 }
26 mark[sum]=i+1;
27 }
28 for(i=a;i<b-1;i++)printf("%d ",i);printf("%d\n",i);
29 }
30 return 0;
31}
32
33
凌晨做tc到快2点
题目描述太难看懂了。
结果看第一个就剩下150分了
然后写完了发现题意没有理解
最后还是wa了啊
一大早起来去给同学买到郑州的火车票，大姐要去找同学玩。
从大同跑到郑州，她爸爸居然都同意了。我那个意外啊。
回来准备一下下午还有一个组队的练习。争取取得好的成绩啊。
摘要: 因为状态很难储存所以款搜是不可以的这个题从网上学了一个好的算法用迭代深搜。每次卡一个深度然后去dfs这样搜到解的时候就是那个卡的深度了。知道方法后很简单
1#include <string.h> 2#include <stdio.h> 3const int N = 25; ...
阅读全文
把所有数字用%x读进来
然后按二进制从第一个开始依次处理就好了
每次先判断这个k的这个位置是0是否可以满足题意如果不可以那便是1
然后每次做一个验证就可以了
1#include<stdio.h>
2int a[8],b[32];
3int main()
4{
5int KASE,i,sum,t,ans,j,l;
6scanf("%d",&KASE);
7while(KASE--)
8{
9for(i=0;i<32;i++)b[i]=0;
10for(i=0;i<8;i++)scanf("%x",&a[i]);
11// for(i=0;i<8;i++)printf("%d ",a[i]);printf("\n");
12scanf("%x",&sum);ans=0;
13for(i=0;i<32;i++)
14{
15t=0;
16for(j=0;j<8;j++)t+=(a[j]^0)&1;
17t=(t+ans)&1;
18if(t==(((sum)^0)&1))b[i]=0;
19else b[i]=1;
20//printf("%d %d %d %d\n",t,(((sum)^0)&1),b[i],i);
21t=0;
22if(b[i]==1)for(j=0;j<8;j++)t+=(a[j]^1)&1;
23else for(j=0;j<8;j++)t+=(a[j]^0)&1;
24for(j=0;j<8;j++)a[j]=a[j]>>1;
25ans=(ans+t)>>1;
26sum=sum>>1;
27}
28ans=0;
29for(i=31;i>=0;i--)
30{
31ans=ans+(b[i]<<i);
32//printf("%d",b[i]);
33// if(i%4==0)printf(" ");
34}
35// printf("\n");
36printf("%x\n",ans);
37}
38return 0;
39}
40
这个题目第一眼看上去准备用数学方法解决
后来看上去数据范围比较小感觉直接枚举就可以了
然后写了个枚举的程序
ax+by=c
然后枚举a动态的保存min=a+b的最小值
当枚举的a>min的时候就停止就可以了
1#include<stdio.h>
2int main()
3{
4 int a,b,c,la,lb,x,y,ansx,ansy,l,min1,min2;
5 while(scanf("%d%d%d",&a,&b,&c),a+b+c)
6 {
7 la=0;
8 min1=1000000000;
9 min2=1000000000;
10 while(1)
11 {
12 if(la>min1 ||la*a>min2)break;
13 l=a*la-c;
14 if(l>=0 && l%b==0)
15 {
16 lb=l/b;
17 x=la;y=lb;
18 if(lb<0)lb=-lb;
19 if(la+lb<min1 ||(la+lb==min1 && la*a+lb*b<min2)){
20 min1=la+lb;
21 min2=la*a+lb*b;
22 ansx=x;ansy=y;
23 }
24 }
25
26 l=c-a*la;
27 if(l>=0 && l%b==0)
28 {
29 lb=l/b;
30 x=la;y=lb;
31 if(lb<0)lb=-lb;
32 if(la+lb<min1 ||(la+lb==min1 && la*a+lb*b<min2)){
33 min1=la+lb;
34 min2=la*a+lb*b;
35 ansx=x;ansy=y;
36 }
37 }
38
39 l=c+a*la;
40 if(l>=0 && l%b==0)
41 {
42 lb=l/b;
43 x=la;y=lb;
44 if(lb<0)lb=-lb;
45 if(la+lb<min1 ||(la+lb==min1 && la*a+lb*b<min2)){
46 min1=la+lb;
47 min2=la*a+lb*b;
48 ansx=x;ansy=y;
49 }
50 }
51 la++;
52 }
53 printf("%d %d\n",ansx,ansy);
54 }
55 return 0;
56}
57
摘要: 这个题目就是一个模拟的过程每次找到一个完整的矩形然后把这个矩形拿出。拿走的地方全部变成**号是可以表示为任何字母然后哦一次下去就可以了。优于把题目读错了结果一直就在wa先开始把题目读成了每个矩形左上角的点和右下角的点必定会出现结果题目的意思是出现的所有点中最靠左的x和最靠上的y组成的就是左上角同样最靠右的最靠下的组成的就是又下角的坐标。
1#include<stdi...
阅读全文
这个题就是一个dp问题
我们用data[i][j]表示前i个数字构成j的方案数
这样的话可以得到状态转移方程
data[i][j]=data[i-1][j-i]+data[i-1][j];
边界条件就是当j等于0的时候data[i][j]=1;
当i等于0的时候j不等于0data[i][j]=0;
然后提交的时候忘记测39这个数据了造成wa了一次
因为求出来的是需要除2的
而39这个数据的答案乘以2以后超过了int
在计算过程中用int64或是unsigned int都是可以的。
我选用了unsigned int这个
因为对g++的int64用哪个一直比较混乱
记得以前写是用long long最近又听说用__int64
1/**//*
2ID: bnugong1
3PROG: subset
4LANG: C++
5*/
6#include<stdio.h>
7#include<string.h>
8unsigned int data[40][800];
9void di(int i,int j)
10{
11 unsigned int ans;
12 if(j==0){
13 data[i][j]=1;
14 return;
15 }
16 if(i==0){
17 data[i][j]=0;
18 return;
19 }
20 if(data[i-1][j]==(unsigned int)-1)di(i-1,j);
21 ans=data[i-1][j];
22 if(j-i>=0){
23 if(data[i-1][j-i]==(unsigned int)-1)di(i-1,j-i);
24 ans+=data[i-1][j-i];
25 }
26 data[i][j]=ans;
27// printf("%d\n",ans);
28 return;
29}
30int main()
31{
32 int n,sum;
33 freopen("subset.in","r",stdin);
34 freopen("subset.out","w",stdout);
35 scanf("%d",&n);
36 sum=((n+1)*n)/2;
37 if(sum%2==1)printf("0\n");
38 else
39 {
40 memset(data,-1,sizeof(data));
41 sum=sum/2;
42 di(n,sum);
43 printf("%u\n",data[n][sum]/2);
44 }
45 return 0;
46}
47
这个题和网上一大牛学了一个很牛的方法。
自己原来的算法就是把所有的都枚举出来然后排序。
大牛的算法很简练。
1/**//*
2ID: bnugong1
3PROG: frac1
4LANG: C++
5*/
6#include<stdio.h>
7int n;
8void di(int a,int b,int c,int d)
9{
10 if(b+d>n)return;
11 di(a,b,a+c,b+d);
12 printf("%d/%d\n",a+c,b+d);
13 di(a+c,b+d,c,d);
14}
15int main()
16{
17 freopen("frac1.in","r",stdin);
18 freopen("frac1.out","w",stdout);
19 scanf("%d",&n);
20 printf("0/1\n");
21 di(0,1,1,1);
22 printf("1/1\n");
23 return 0;
24}
25