這個題目先開始一直沒有好的想法。
題目也是看了很久才看懂
師姐先開始的想法很好但是我沒有去做。
最后兜了很大一個圈子還是回到了以前的想法
就是模擬的去建一個數然后給每個位置標號沒上成一層就加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