ACM

简单贪心…. 需要注意的是数据是非负，所以有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掉了。。。。杭电数据略水？