111qqz

I NEED A OFFER! # **Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 18287 Accepted Submission(s): 7320 ** Problem Description Speakless很早就想出国，现在他已经考完了所有需要的考试，准备了所有要准备的材料，于是，便需要去申请学校了。要申请国外的任何大学，你都要交纳一定的申请费用，这可是很惊人的。Speakless没有多少钱，总共只攒了n万美元。他将在m个学校中选择若干的（当然要在他的经济承受范围内）。每个学校都有不同的申请费用a（万美元），并且Speakless估计了他得到这个学校offer的可能性b。不同学校之间是否得到offer不会互相影响。“I NEED A OFFER”，他大叫一声。帮帮这个可怜的人吧，帮助他计算一下，他可以收到至少一份offer的最大概率。（如果Speakless选择了多个学校，得到任意一个学校的offer都可以）。

饭卡 # **Time Limit: 5000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 14225 Accepted Submission(s): 4945 ** Problem Description 电子科大本部食堂的饭卡有一种很诡异的设计，即在购买之前判断余额。如果购买一个商品之前，卡上的剩余金额大于或等于5元，就一定可以购买成功（即使购买后卡上余额为负），否则无法购买（即使金额足够）。所以大家都希望尽量使卡上的余额最少。 某天，食堂中有n种菜出售，每种菜可购买一次。已知每种菜的价格以及卡上的余额，问最少可使卡上的余额为多少。

ZCC Loves Codefires Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 988 Accepted Submission(s): 500 Problem Description Though ZCC has many Fans, ZCC himself is a crazy Fan of a coder, called “Memset137”. It was on Codefires(CF), an online competitive programming site, that ZCC knew Memset137, and immediately became his fan. But why? Because Memset137 can solve all problem in rounds, without unsuccessful submissions; his estimation of time to solve certain problem is so accurate, that he can surely get an Accepted the second he has predicted. He soon became IGM, the best title of Codefires. Besides, he is famous for his coding speed and the achievement in the field of Data Structures. After become IGM, Memset137 has a new goal: He wants his score in CF rounds to be as large as possible. What is score? In Codefires, every problem has 2 attributes, let’s call them Ki and Bi(Ki, Bi＞0). if Memset137 solves the problem at Ti-th second, he gained Bi-KiTi score. It’s guaranteed Bi-KiTi is always positive during the round time. Now that Memset137 can solve every problem, in this problem, Bi is of no concern. Please write a program to calculate the minimal score he will lose.(that is, the sum of Ki*Ti).

Wooden Sticks Time Limit: 1000MS Memory Limit: 10000K Total Submissions: 19008 Accepted: 8012 Description There is a pile of n wooden sticks. The length and weight of each stick are known in advance. The sticks are to be processed by a woodworking machine in one by one fashion. It needs some time, called setup time, for the machine to prepare processing a stick. The setup times are associated with cleaning operations and changing tools and shapes in the machine. The setup times of the woodworking machine are given as follows: (a) The setup time for the first wooden stick is 1 minute. (b) Right after processing a stick of length l and weight w , the machine will need no setup time for a stick of length l’ and weight w’ if l <= l’ and w <= w’. Otherwise, it will need 1 minute for setup. You are to find the minimum setup time to process a given pile of n wooden sticks. For example, if you have five sticks whose pairs of length and weight are ( 9 , 4 ) , ( 2 , 5 ) , ( 1 , 2 ) , ( 5 , 3 ) , and ( 4 , 1 ) , then the minimum setup time should be 2 minutes since there is a sequence of pairs ( 4 , 1 ) , ( 5 , 3 ) , ( 9 , 4 ) , ( 1 , 2 ) , ( 2 , 5 ) . Input

简单贪心。 因为填的字母没有次数限制，所以最优策略很容易想到，就是在最后面填最大的。 不用实际去填，算出ans就可以。 1 2 3 4 #include <iostream> 5 #include <cmath> 6 #include <cstring> 7 #include <algorithm> 8 9 using namespace std; 10 11 int main() 12 { 13 int k,len; 14 char st[2000]; 15 int a[2000]; 16 memset(a,0,sizeof(a)); 17 int w[50]; 18 cin>>st>>k; 19 int m=-1; 20 for (int i=1;i<=26;i++) 21 { 22 23 cin>>w[i]; 24 if (w[i]>m) 25 m=w[i]; 26 } 27 len=strlen(st); 28 for (int i=0;i<len;i++) 29 a[i]=(int)(st[i]-96); 30 long long ans=0; 31 for (int i=0;i<len;i++) 32 { 33 ans=ans+w[a[i]]*(i+1); 34 // cout<<ans<<endl; 35 } 36 for (int i=len;i<len+k;i++) 37 ans=ans+m*(i+1); 38 cout<<ans<<endl; 39 return 0; 40 }

简单贪心…. 需要注意的是数据是非负，所以有0的情况要考虑周全，基本都要特殊处理。 多WA了三次，不知道为什么交C++可以过，交G++就不行。 代码实现 1 2 /* *********************************************** 3 Author :111qqz 4 Created Time :2016年02月19日 星期五 16时38分28秒 5 File Name :code/hdu/1009.cpp 6 ************************************************ */ 7 8 #include <iostream> 9 #include <cstring> 10 #include <algorithm> 11 #include <cstdio> 12 #include <iomanip> 13 14 using namespace std; 15 16 int main() 17 { 18 int m,n,f[1500],j[1500]; 19 double scale[1500]; 20 double ans,sum; 21 while(scanf("%d %d",&m,&n)!=EOF&&(m!=-1)) 22 { ans=0; 23 // if (m==0) 24 memset(scale,0,sizeof(scale)); 25 memset(f,0,sizeof(f)); 26 memset(j,0,sizeof(j)); 27 // bool flag=false; 28 for (int i=1;i<=n;i++) 29 { 30 scanf("%d %d",&j[i],&f[i]); 31 if (f[i]!=0) 32 scale[i]=(double)j[i]*1.0/f[i]; 33 else if (j[i]!=0) 34 { 35 ans=ans+j[i]; 36 37 } 38 } 39 // if (flag) {cout<<fixed<<setprecision(3)<<ans<<endl;continue;} 40 for (int i=1;i<=n-1;i++) 41 for (int k=i+1;k<=n;k++) 42 if (scale[i]<scale[k]) 43 { 44 swap(scale[i],scale[k]); 45 swap(j[i],j[k]); 46 swap(f[i],f[k]); 47 } 48 sum=0; 49 int i=1; 50 while (m>=sum&&i<=n) 51 { 52 ans=ans+j[i]; 53 sum=sum+f[i]; 54 i++; 55 } 56 i--; 57 ans=ans-j[i]; 58 sum=sum-f[i]; 59 ans=ans+(m-sum)*scale[i]; 60 cout<<fixed<<setprecision(3)<<ans<<endl; 61 62 63 } 64 return 0; 65 }

一开始算法想的有点问题。 坑点在于走廊两侧都有房间 也就是说room1和room2对应的位置是一样的 1 to 3 4to6 是没法同时完成的。 做法就是整个扫一遍，看哪个位置的重复次数最大，*10就是答案。

题意：求两个相等的圆环的相交的面积…. 简单计算几何+容斥原理？ 扇形面积公式记错调了半天2333333333 这题不难…倒是从学长那里收获了几点关于代码规范的问题… 听说了学长在北京区域赛时把PI定义错了一位结果一直WA的教训…. 以后还是写acos(-1)吧 局部变量和全局变量因为【想怎么其变量名想得整个人都不好了】就起成了一样的…被学长给了差评。 哦，对！还有一个就是发现了cmath库里有一个奇葩的函数名叫y1.。。。。。。。 —————————————————————————————————————————————— 竟然CE了 提示 error:pow(int,int) is ambiguous 看来我对语言的掌握程度还是不行呀…..

Description Matt has N friends. They are playing a game together. Each of Matt’s friends has a magic number. In the game, Matt selects some (could be zero) of his friends. If the xor (exclusive-or) sum of the selected friends’magic numbers is no less than M , Matt wins. Matt wants to know the number of ways to win. Input The first line contains only one integer T , which indicates the number of test cases.

题意是说用 k 种颜色填充 nm 的方格，第 i 种颜色要用 c[i] 次，保证 c[i]（i 属于 1..k）的和为 nm，问是否有可行解，若有，输出任意一种。 第一感觉是 dfs，而且数据范围还那么小。但是鉴于我上次 dfs 写成汪的经历……嗯，不过群里有学长说似乎剪枝不太好想？ 我一开始分了四类：o 行 o 列、e 行 e 列、e 行 o 列、o 行 e 列（o 是 odd，e 是 even），然后将 c[i] 排序，先填大的 c[i]，感觉这样应该更容易找到解。交了一发，WA 掉了。发现当 k 较小的时候，也就是 c[i] 都相对较大的时候，先填大的 c[i] 的策略会出现错误。于是我换了下，按 c[i] 的大小从两边往中间填。然后我还发现其实 o 行 o 列和 e 行 e 列可以归为一类，同理，后两种也可以归为一类。又交，又 WA 2333333。然后想了好久，发现对于上面说的两类的处理顺序不同会得到不同的结果，只有一种是对的。于是加了个 judge 函数判断冲突，如果冲突就换个顺序。再交，A 了。