Posts

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 了。

ACM STEPS里的…这题前面一道是求LCM….结果接下来就是这么一道。。。 朴素会超….筛法会爆….题目顺序真是按照难度来的？ 于是想到 Miller-Rabin素数测试……. 这个方法是基于费马小定理 我的理解就是… 如果我要判断n是否为素数 只要取k个数 如果满足 a^(n-1)mod n =1 那么n就很可能为素数。 证明什么的…暂时还是算了吧…论文里貌似扯了一大堆 第一次用，竟然真的A了。。。。 感觉更好的办法也许是先打一个比较小的素数表，然后每次random选取若干个进行判断…那样应该更可靠些？ 本来想WA掉之后再改的。。。没想到这么写就A掉了。。。。杭电数据略水？