水题,推个公式出来,注意精度…一遍A
1 2 /************************************************************************* 3 > File Name: code/2015summer/#5/D.cpp 4 > Author: 111qqz 5 > Email: rkz2013@126.com 6 > Created Time: 2015年07月30日 星期四 13时17分26秒 7 ************************************************************************/ 8 9 #include<iostream> 10 #include<iomanip> 11 #include<cstdio> 12 #include<algorithm> 13 #include<cmath> 14 #include<cstring> 15 #include<string> 16 #include<map> 17 #include<set> 18 #include<queue> 19 #include<vector> 20 #include<stack> 21 #define y0 abc111qqz 22 #define y1 hust111qqz 23 #define yn hez111qqz 24 #define j1 cute111qqz 25 #define tm crazy111qqz 26 #define lr dying111qqz 27 using namespace std; 28 #define REP(i, n) for (int i=0;i<int(n);++i) 29 typedef long long LL; 30 typedef unsigned long long ULL; 31 const int inf = 0x7fffffff; 32 int s,m,p; 33 double ans; 34 35 double cal(double x,int n) 36 { 37 double res = 1.0; 38 for ( int i = 1 ; i <= n ; i++ ) 39 { 40 res = res * x; 41 } 42 // cout<<"res:"<<res<<endl; 43 return res; 44 } 45 int main() 46 { 47 cin>>s>>m>>p; 48 double sum = 0; 49 double per = p*1.0/100+1; 50 for ( int i = 1 ; i <= m; i++ ) 51 { 52 sum=sum+1.0/cal(per,i); 53 // cout<<"sum:"<<sum<<endl; 54 } 55 // cout<<sum<<endl; 56 cout<<fixed<<setprecision(5)<<s*1.0/sum<<endl; 57 58 return 0; 59 }
AMR10F - Cookies Piles # 水.
Sliding Window
看这个问题：An array of size n ≤ 106 is given to you. There is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves rightwards by one position.Your task is to determine the maximum and minimum values in the sliding window at each position.
快要炸了..
tle成狗
因为是tle,看了下自己没有写cin cout,估计就是算法的问题…
C. Artem and Array
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
Artem has an array of n positive integers. Artem decided to play with it. The game consists of n moves. Each move goes like this. Artem chooses some element of the array and removes it. For that, he gets min(a, b) points, where a and b are numbers that were adjacent with the removed number. If the number doesn’t have an adjacent number to the left or right, Artem doesn’t get any points.
B. Andrey and Problem
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
Andrey needs one more problem to conduct a programming contest. He has n friends who are always willing to help. He can ask some of them to come up with a contest problem. Andrey knows one value for each of his fiends – the probability that this friend will come up with a problem if Andrey asks him.
B. Kolya and Tandem Repeat
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
Kolya got string s for his birthday, the string consists of small English letters. He immediately added k more characters to the right of the string.
比赛的时候没做出来.这道题需要用到的一个重要的性质是,任意一个自然数可以表示成至多三个三角形数(1,3,6,10,15…..)的和(orz高斯)然后也有推广到任意自然数可以表示成k个k角形数的和的结论(费马提出了猜想,柯西给了证明)然后官方题解说的比较好:
它有一定的规律性，排列如下(构成图)，像上面的1、3、6、10、15等等这些能够表示成三角形的形状的总数量的数，叫做三角形数。
http://acm.hdu.edu.cn/showproblem.php?pid=5311 题意：问能否从一个给定的字符串中拿出三个不相交的字串（原串可以有剩余），组成字符串“anniversary” 思路：暴力。
http://acm.hdu.edu.cn/showproblem.php?pid=5310 水。 不要用cin.
1 2 /************************************************************************* 3 > File Name: code/bc/#ann/1001.cpp 4 > Author: 111qqz 5 > Email: rkz2013@126.com 6 > Created Time: 2015年07月25日 星期六 18时54分24秒 7 ************************************************************************/ 8 9 #include<iostream> 10 #include<iomanip> 11 #include<cstdio> 12 #include<algorithm> 13 #include<cmath> 14 #include<cstring> 15 #include<string> 16 #include<map> 17 #include<set> 18 #include<queue> 19 #include<vector> 20 #include<stack> 21 #define y0 abc111qqz 22 #define y1 hust111qqz 23 #define yn hez111qqz 24 #define j1 cute111qqz 25 #define tm crazy111qqz 26 #define lr dying111qqz 27 using namespace std; 28 #define REP(i, n) for (int i=0;i<int(n);++i) 29 typedef long long LL; 30 typedef unsigned long long ULL; 31 int n,m,p,q; 32 int main() 33 { 34 int T; 35 cin>>T; 36 int ans = 0; 37 while (T--) 38 { 39 // scanf("%d %d %d %d",&n,&m,&p,&q); 40 scanf("%d %d %d %d",&n,&m,&p,&q); 41 ans = n*p; 42 ans = min(ans,n/m*q+n%m*p); 43 ans = min(ans,((n-1)/m+1)*q); 44 printf("%d\n",ans); 45 } 46 47 return 0; 48 }
“… so forward this to ten other people, to prove that you believe the emperor has
题意是说发短信,每个人只会给一个人发,问从哪个人开始发,能传到的人最多
http://acm.hust.edu.cn/vjudge/contest/view.action?cid=83084#problem/I
I - Fire Game
**Time Limit:**1000MS **Memory Limit:**32768KB 64bit IO Format:%I64d & %I64u
Submit Status
Description
Fat brother and Maze are playing a kind of special (hentai) game on an N*M board (N rows, M columns). At the beginning, each grid of this board is consisting of grass or just empty and then they start to fire all the grass. Firstly they choose two grids which are consisting of grass and set fire. As we all know, the fire can spread among the grass. If the grid (x, y) is firing at time t, the grid which is adjacent to this grid will fire at time t+1 which refers to the grid (x+1, y), (x-1, y), (x, y+1), (x, y-1). This process ends when no new grid get fire. If then all the grid which are consisting of grass is get fired, Fat brother and Maze will stand in the middle of the grid and playing a MORE special (hentai) game. (Maybe it’s the OOXX game which decrypted in the last problem, who knows.)
好爽,一遍ac
1 2 3 /************************************************************************* 4 > File Name: code/2015summer/searching/H.cpp 5 > Author: 111qqz 6 > Email: rkz2013@126.com 7 > Created Time: 2015年07月27日 星期一 09时11分28秒 8 ************************************************************************/ 9 10 #include<iostream> 11 #include<iomanip> 12 #include<cstdio> 13 #include<algorithm> 14 #include<cmath> 15 #include<cstring> 16 #include<string> 17 #include<map> 18 #include<set> 19 #include<queue> 20 #include<vector> 21 #include<stack> 22 #define y0 abc111qqz 23 #define y1 hust111qqz 24 #define yn hez111qqz 25 #define j1 cute111qqz 26 #define tm crazy111qqz 27 #define lr dying111qqz 28 using namespace std; 29 #define REP(i, n) for (int i=0;i<int(n);++i) 30 typedef long long LL; 31 typedef unsigned long long ULL; 32 const int N=1E2+5; 33 int A,B,C; 34 int d[N][N]; 35 bool flag; 36 struct node 37 { 38 int d,opt,par,prea,preb; 39 }q[N][N]; 40 41 void print(int x,int y) 42 { 43 // cout<<"x:"<<x<<"y:"<<y<<endl; 44 if (q[x][y].prea!=-1&&q[x][y].preb!=-1) 45 { 46 // cout<<"who is 111qqz"<<endl; 47 print(q[x][y].prea,q[x][y].preb); 48 if (q[x][y].opt==1){ 49 printf("FILL(%d)\n",q[x][y].par); 50 } 51 if (q[x][y].opt==2) 52 { 53 printf("DROP(%d)\n",q[x][y].par); 54 } 55 if (q[x][y].opt==3) 56 { 57 printf("POUR(%d,%d)\n",q[x][y].par,3-q[x][y].par); 58 } 59 } 60 61 } 62 void bfs() 63 { 64 memset(q,-1,sizeof(q)); 65 queue<int>a; 66 queue<int>b; 67 a.push(0); 68 b.push(0); 69 q[0][0].d=0; 70 while (!a.empty()&&!b.empty()) 71 { 72 int av = a.front();a.pop(); 73 int bv = b.front();b.pop(); 74 // cout<<"av:"<<av<<"bv:"<<bv<<endl; 75 if (av==C||bv==C) 76 { 77 flag = true; 78 //cout<<"yeah~~~~~~~~~~~~~~~"<<endl; 79 cout<<q[av][bv].d<<endl; 80 // cout<<"prea:"<<q[av][bv].prea<<"preb:"<<q[av][bv].preb<<endl; 81 print(av,bv); 82 return; 83 } 84 if (av<A&&q[A][bv].d==-1) 85 { 86 q[A][bv].d=q[av][bv].d+1; 87 q[A][bv].opt=1; 88 q[A][bv].par=1; 89 q[A][bv].prea=av; 90 q[A][bv].preb=bv; 91 a.push(A); 92 b.push(bv); 93 } 94 if (av>0&&q[0][bv].d==-1) 95 { 96 q[0][bv].d=q[av][bv].d+1; 97 q[0][bv].opt=2; 98 q[0][bv].par=1; 99 q[0][bv].prea=av; 100 q[0][bv].preb=bv; 101 a.push(0); 102 b.push(bv); 103 104 } 105 if (bv<B&&q[av][B].d==-1) 106 { 107 q[av][B].d=q[av][bv].d+1; 108 q[av][B].opt=1; 109 q[av][B].par=2; 110 q[av][B].prea = av; 111 q[av][B].preb = bv; 112 a.push(av); 113 b.push(B); 114 115 } 116 if (bv>0&&q[av][0].d==-1) 117 { 118 q[av][0].d=q[av][bv].d+1; 119 q[av][0].opt=2; 120 q[av][0].par=2; 121 q[av][0].prea=av; 122 q[av][0].preb=bv; 123 a.push(av); 124 b.push(0); 125 } 126 127 if (av+bv<=B&&q[0][av+bv].d==-1) 128 { 129 q[0][av+bv].d=q[av][bv].d+1; 130 q[0][av+bv].opt=3; 131 q[0][av+bv].par=1; 132 q[0][av+bv].prea=av; 133 q[0][av+bv].preb=bv; 134 a.push(0); 135 b.push(av+bv); 136 } 137 if (av+bv>B&&q[av-(B-bv)][B].d==-1) //把1往2里倒入的两种情况 138 { 139 140 int tmp = av-(B-bv); 141 q[tmp][B].d=q[av][bv].d+1; 142 q[tmp][B].opt=3; 143 q[tmp][B].par=1; 144 q[tmp][B].prea=av; 145 q[tmp][B].preb=bv; 146 a.push(tmp); 147 b.push(B); 148 } 149 150 if (bv+av<=A&&q[av+bv][0].d==-1) 151 { 152 q[av+bv][0].d=q[av][bv].d+1; 153 q[av+bv][0].opt=3; 154 q[av+bv][0].par=2; 155 q[av+bv][0].prea=av; 156 q[av+bv][0].preb=bv; 157 a.push(av+bv); 158 b.push(0); 159 } 160 if (bv+av>A&&q[A][bv-(A-av)].d==-1) 161 { 162 int tmp = bv-(A-av); 163 q[A][tmp].d=q[av][bv].d+1; 164 q[A][tmp].opt=3; 165 q[A][tmp].par=2; 166 q[A][tmp].prea=av; 167 q[A][tmp].preb=bv; 168 a.push(A); 169 b.push(tmp); 170 } 171 } 172 } 173 int main() 174 { 175 176 flag = false; 177 cin>>A>>B>>C; 178 bfs(); 179 if (!flag) 180 { 181 cout<<"impossible"<<endl; 182 } 183 184 185 return 0; 186 }
非常可乐 # **Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 7194 Accepted Submission(s): 2865 **
Oil Deposits # **Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 17683 Accepted Submission(s): 10172 **
Find a way # ****Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 6221 Accepted Submission(s): 2070 **
迷宫问题
1 2 3 4 /************************************************************************* 5 > File Name: code/2015summer/searching/KK.cpp 6 > Author: 111qqz 7 > Email: rkz2013@126.com 8 > Created Time: 2015年07月25日 星期六 13时33分00秒 9 ************************************************************************/ 10 11 #include<iostream> 12 #include<iomanip> 13 #include<cstdio> 14 #include<algorithm> 15 #include<cmath> 16 #include<cstring> 17 #include<string> 18 #include<map> 19 #include<set> 20 #include<queue> 21 #include<vector> 22 #include<stack> 23 #define y0 abc111qqz 24 #define y1 hust111qqz 25 #define yn hez111qqz 26 #define j1 cute111qqz 27 #define tm crazy111qqz 28 #define lr dying111qqz 29 using namespace std; 30 #define REP(i, n) for (int i=0;i<int(n);++i) 31 typedef long long LL; 32 typedef unsigned long long ULL; 33 int a[10][10]; 34 int head = 0; 35 int tail = 1; 36 int dirx[2]={1,0}; 37 int diry[2]={0,1}; 38 struct node 39 { 40 int x,y,pre; 41 }q[10]; 42 43 void print(int x) 44 { 45 if (q[x].pre!=-1) 46 { 47 print(q[x].pre); 48 printf("(%d, %d)\n",q[x].x,q[x].y); 49 } 50 } 51 void bfs() 52 { 53 q[head].x=0; 54 q[head].y=0; 55 q[head].pre=-1; 56 while (head<tail) 57 { 58 if (q[head].x==4&&q[head].y==4) 59 { 60 print(head); 61 return; 62 } 63 for (int i = 0 ; i < 2 ; i++ ) 64 { 65 int newx=dirx[i]+q[head].x; 66 int newy=diry[i]+q[head].y; 67 if (newx>=0&&newx<5&&newy>=0&&newy<5&&a[newx][newy]==0) 68 { 69 q[tail].x=newx; 70 q[tail].y=newy; 71 q[tail].pre=head; 72 tail++; 73 } 74 } 75 head++; 76 } 77 78 } 79 int main() 80 { 81 for ( int i = 0 ; i < 5 ; i++ ) 82 { 83 for ( int j = 0 ; j < 5; j++) 84 { 85 cin>>a[i][j]; 86 } 87 } 88 printf("(0, 0)\n"); 89 bfs(); 90 91 return 0; 92 }
http://poj.org/problem?id=3087
用bfs写的，但是其实就是个模拟啊喂！
只有一种操作，何谈最短？ 一直往下写就行了．
http://poj.org/problem?id=3126
题意是说,给定两个四位素数a b 问从a变换到b,最少需要变换几次. 变换的要求是,每次只能改变一个数字,而且中间过程得到的四位数也必须为素数. 因为提到最少变换几次,容易想到bfs,bfs第一次搜到的一定是最短步数.
