国家集训队论文分类整理

距离ACM/ICPC的时间越来越少了,选择性地看一些集训队论文是很有必要的。

组合数学 计数与统计 2001 - 符文杰:《Pólya原理及其应用》
2003 - 许智磊:《浅谈补集转化思想在统计问题中的应用》
2007 - 周冬:《生成树的计数及其应用》
2008 - 陈瑜希《Pólya计数法的应用》
数位问题 2009 - 高逸涵《数位计数问题解法研究》
2009 - 刘聪《浅谈数位类统计问题》
动态统计 2004 - 薛矛:《解决动态统计问题的两把利刃》
2007 - 余江伟:《如何解决动态统计问题》
博弈 2002 - 张一飞:《由感性认识到理性认识——透析一类搏弈游戏的解答过程》
2007 - 王晓珂:《解析一类组合游戏》
2009 - 曹钦翔《从“k倍动态减法游戏”出发探究一类组合游戏问题》
2009 - 方展鹏《浅谈如何解决不平等博弈问题》
2009 - 贾志豪《组合游戏略述——浅谈SG游戏的若干拓展及变形》
母函数 2009 - 毛杰明《母函数的性质及应用》
拟阵 2007 - 刘雨辰:《对拟阵的初步研究》
线性规划 2007 - 李宇骞:《浅谈信息学竞赛中的线性规划——简洁高效的单纯形法实现与应用》
置换群 2005 - 潘震皓:《置换群快速幂运算研究与探讨》
问答交互 2003 - 高正宇:《答案只有一个——浅谈问答式交互问题》 
猜数问题 2003 - 张宁:《猜数问题的研究:<聪明的学生>一题的推广》
2006 - 龙凡:《一类猜数问题的研究》
数据结构 数据结构 2005 - 何林:《数据关系的简化》
2006 - 朱晨光:《基本数据结构在信息学竞赛中的应用》
2007 - 何森:《浅谈数据的合理组织》
2008 - 曹钦翔《数据结构的提炼与压缩》
结构联合 2001 - 高寒蕊:《从圆桌问题谈数据结构的综合运用》
2005 - 黄刚:《数据结构的联合》
块状链表 2005 - 蒋炎岩:《数据结构的联合——块状链表》
2008 - 苏煜《对块状链表的一点研究》
动态树 2006 - 陈首元:《维护森林连通性——动态树》
2007 - 袁昕颢:《动态树及其应用》
左偏树 2005 - 黄源河:《左偏树的特点及其应用》
跳表 2005 - 魏冉:《让算法的效率“跳起来”!——浅谈“跳跃表”的相关操作及其应用》
2009 - 李骥扬《线段跳表——跳表的一个拓展》
SBT 2007 - 陈启峰:《Size Balance Tree》
线段树 2004 - 林涛:《线段树的应用》
单调队列 2006 - 汤泽:《浅析队列在一类单调性问题中的应用》
哈希表 2005 - 李羽修:《Hash函数的设计优化》
2007 - 杨弋:《Hash在信息学竞赛中的一类应用》
Splay 2004 - 杨思雨:《伸展树的基本操作与应用》
图论 图论 2005 - 任恺:《图论的基本思想及方法》
模型建立 2004 - 黄源河:《浅谈图论模型的建立与应用》
2004 - 肖天:《“分层图思想”及其在信息学竞赛中的应用》
网络流 2001 - 江鹏:《从一道题目的解法试谈网络流的构造与算法》
2002 - 金恺:《浅谈网络流算法的应用》
2007 - 胡伯涛:《最小割模型在信息学竞赛中的应用》
2007 - 王欣上:《浅谈基于分层思想的网络流算法》
2008 - 周冬《两极相通——浅析最大—最小定理在信息学竞赛中的应用》
最短路 2006 - 余远铭:《最短路算法及其应用》
2008 - 吕子鉷《浅谈最短径路问题中的分层思想》
2009 - 姜碧野《SPFA算法的优化及应用》
欧拉路 2007 - 仇荣琦:《欧拉回路性质与应用探究》
差分约束系统 2006 - 冯威:《数与图的完美结合——浅析差分约束系统》
平面图 2003 - 刘才良:《平面图在信息学中的应用》
2007 - 古楠:《平面嵌入》
2-SAT 2003 - 伍昱:《由对称性解2-SAT问题》
最小生成树 2004 - 吴景岳:《最小生成树算法及其应用》
2004 - 汪汀:《最小生成树问题的拓展》
二分图 2005 - 王俊:《浅析二分图匹配在信息学竞赛中的应用》
Voronoi图 2006 - 王栋:《浅析平面Voronoi图的构造及应用》
偶图 2002 - 孙方成:《偶图的算法及应用》
2002 - 周文超:《树结构在程序设计中的运用》
2005 - 栗师:《树的乐园——一些与树有关的题目》
路径问题 2009 - 漆子超《分治算法在树的路径问题中的应用》
最近公共祖先 2007 - 郭华阳:《RMQ与LCA问题》
划分问题 2004 - 贝小辉:《浅析树的划分问题》
数论 欧几里得算法 2009 - 金斌《欧几里得算法的应用》
同余方程 2003 - 姜尚仆:《模线性方程的应用——用数论方法解决整数问题》
搜索 搜索 2001 - 骆骥:《由“汽车问题”浅谈深度搜索的一个方面——搜索对象与策略的重要性》
2002 - 王知昆:《搜索顺序的选择》
2005 - 汪汀:《参数搜索的应用》
启发式 2009 - 周而进《浅谈估价函数在信息学竞赛中的应用》
优化 2003 - 金恺:《探寻深度优先搜索中的优化技巧——从正方形剖分问题谈起》
2003 - 刘一鸣:《一类搜索的优化思想——数据有序化》
2006 - 黄晓愉:《深度优先搜索问题的优化技巧》
背包问题 2009 - 徐持衡《浅谈几类背包题》
匹配 2004 - 楼天城:《匹配算法在搜索问题中的巧用》
概率 概率 2009 - 梅诗珂《信息学竞赛中概率问题求解初探》
数学期望 2009 - 汤可因《浅析竞赛中一类数学期望问题的解决方法》
字符串 字符串 2003 - 周源:《浅析“最小表示法”思想在字符串循环同构问题中的应用》
多串匹配 2004 - 朱泽园:《多串匹配算法及其启示》
2006 - 王赟:《Trie图的构建、活用与改进》
2009 - 董华星《浅析字母树在信息学竞赛中的应用》
后缀数组 2004 - 许智磊:《后缀数组》
2009 - 罗穗骞《后缀数组——处理字符串的有力工具》
字符串匹配 2003 - 饶向荣:《病毒的DNA———剖析一道字符匹配问题解析过程》
2003 - 林希德:《求最大重复子串》
动态规划 动态规划 2001 - 俞玮:《基本动态规划问题的扩展》
2006 - 黄劲松:《贪婪的动态规划》
2009 - 徐源盛《对一类动态规划问题的研究》
状态压缩 2008 - 陈丹琦《基于连通性状态压缩的动态规划问题》
状态设计 2008 - 刘弈《浅谈信息学中状态的合理设计与应用》
树形DP 2007 - 陈瑜希:《多角度思考创造性思维——运用树型动态规划解题的思路和方法探析》
优化 2001 - 毛子青:《动态规划算法的优化技巧》
2003 - 项荣璟:《充分利用问题性质——例析动态规划的“个性化”优化》
2004 - 朱晨光:《优化,再优化!——从《鹰蛋》一题浅析对动态规划算法的优化》
2007 - 杨哲:《凸完全单调性的加强与应用》
计算几何 立体几何 2003 - 陆可昱:《长方体体积并》
2008 - 高亦陶《从立体几何问题看降低编程复杂度》
计算几何思想 2004 - 金恺:《极限法——解决几何最优化问题的捷径》
2008 - 程芃祺《计算几何中的二分思想》
2008 - 顾研《浅谈随机化思想在几何问题中的应用》
2007 - 高逸涵:《与圆有关的离散化》
半平面交 2002 - 李澎煦:《半平面交的算法及其应用》
2006 - 朱泽园:《半平面交的新算法及其实用价值》
矩阵 矩阵 2008 - 俞华程《矩阵乘法在信息学中的应用》
高斯消元 2002 - 何江舟:《用高斯消元法解线性方程组》
数学方法 数学思想 2002 - 何林:《猜想及其应用》
2003 - 邵烜程:《数学思想助你一臂之力》
数学归纳法 2009 - 张昆玮《数学归纳法与解题之道》
多项式 2002 - 张家琳:《多项式乘法》
数形结合 2004 - 周源:《浅谈数形结合思想在信息学竞赛中的应用》
黄金分割 2005 - 杨思雨:《美,无处不在——浅谈“黄金分割”和信息学的联系》
其他算法 遗传算法 2002 - 张宁:《遗传算法的特点及其应用》
2005 - 钱自强:《关于遗传算法应用的分析与研究》
信息论 2003 - 侯启明:《信息论在信息学竞赛中的简单应用》
染色与构造 2002 - 杨旻旻:《构造法——解题的最短路径》
2003 - 方奇:《染色法和构造法在棋盘上的应用》
一类问题 区间 2008 - 周小博《浅谈信息学竞赛中的区间问题》
2005 - 龙凡:《序的应用》
2006 - 汪晔:《信息学中的参考系与坐标系》
物理问题 2008 - 方戈《浅析信息学竞赛中一类与物理有关的问题》
编码与译码 2008 - 周梦宇《码之道—浅谈信息学竞赛中的编码与译码问题》
对策问题 2002 - 骆骥:《浅析解“对策问题”的两种思路》
优化 算法优化 2002 - 孙林春:《让我们做得更好——从解法谈程序优化》
2004 - 胡伟栋:《减少冗余与算法优化》
2005 - 杨弋:《从<小H的小屋>的解法谈算法的优化》
2006 - 贾由:《由图论算法浅析算法优化》
程序优化 2006 - 周以苏:《论反汇编在时间常数优化中的应用》
2009 - 骆可强《论程序底层优化的一些方法与技巧》
语言 C++ 2004 - 韩文弢:《论C++语言在信息学竞赛中的应用》
策略 策略 2004 - 李锐喆:《细节——不可忽视的要素》
2005 - 朱泽园:《回到起点——一种突破性思维》
2006 - 陈启峰:《“约制、放宽”方法在解题中的应用》
2006 - 李天翼:《从特殊情况考虑》
2007 - 陈雪:《问题中的变与不变》
2008 - 肖汉骏《例谈信息学竞赛分析中的“深”与“广”》
倍增 2005 - 朱晨光:《浅析倍增思想在信息学竞赛中的应用》
二分 2002 - 李睿:《二分法与统计问题》
2002 - 许智磊:《二分,再二分!——从Mobiles(IOI2001)一题看多重二分》
2005 - 杨俊:《二分策略在信息学竞赛中的应用》
调整 2006 - 唐文斌:《“调整”思想在信息学中的应用》
随机化 2007 - 刘家骅:《浅谈随机化在信息学竞赛中的应用》
非完美算法 2005 - 胡伟栋:《浅析非完美算法在信息学竞赛中的应用》
2008 - 任一恒《非完美算法初探》
提交答案题 2003 - 雷环中:《结果提交类问题》
守恒思想 2004 - 何林:《信息学中守恒法的应用》
极限法 2003 - 王知昆:《浅谈用极大化思想解决最大子矩形问题》
贪心 2008 - 高逸涵《部分贪心思想在信息学竞赛中的应用》
压缩法 2005 - 周源:《压去冗余缩得精华——浅谈信息学竞赛中的“压缩法”》
逆向思维 2005 - 唐文斌:《正难则反——浅谈逆向思维在解题中的应用》
穷举 2004 - 鬲融:《浅谈特殊穷举思想的应用》
目标转换 2002 - 戴德承:《退一步海阔天空——“目标转化思想”的若干应用》
2004 - 栗师:《转化目标在解题中的应用》
类比 2006 - 周戈林:《浅谈类比思想》
分割与合并 2006 - 俞鑫:《棋盘中的棋盘——浅谈棋盘的分割思想》
2007 - 杨沐:《浅析信息学中的“分”与“合”》
平衡思想 2008 - 郑暾《平衡规划——浅析一类平衡思想的应用》

CF 1A(隐式转换)

A. Theatre Square
time limit per test

2 seconds

memory limit per test

64 megabytes

input

standard input

output

standard output

在n*m的广场上平铺边长为a的正方形石板,问至少要多少石板才能铺满广场(石板必须对齐且与边角线平行)

Input

输入仅一行 n,  m and a (1 ≤  n, m, a ≤ 109).

Output

输出一行最小石板数。

Sample test(s)
input
6 6 4
output
4

显然答案为(ceil(double(n)/double(a))*ceil(double(m)/double(a)))。

但直接用cout输出可能被转换成科学表示法

且极端情况Maxn*Maxm>2^31

所以输出时要打上(long long)

而且必须框上double()否则中间的‘/'会被当成整除


#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<iostream>
using namespace std;
#define MAXN (1000000000)
long long n,m,a;
int main()
{
	cin>>n>>m>>a;
	cout<<(long long)(ceil(double(n)/double(a))*ceil(double(m)/double(a)))<<endl;
	return 0;
}

HDU 1166(zkw线段树-单点修改)

敌兵布阵

Problem Description
C国的死对头A国这段时间正在进行军事演习,所以C国间谍头子Derek和他手下Tidy又开始忙乎了。A国在海岸线沿直线布置了N个工兵营地,Derek和Tidy的任务就是要监视这些工兵营地的活动情况。由于采取了某种先进的监测手段,所以每个工兵营地的人数C国都掌握的一清二楚,每个工兵营地的人数都有可能发生变动,可能增加或减少若干人手,但这些都逃不过C国的监视。
中央情报局要研究敌人究竟演习什么战术,所以Tidy要随时向Derek汇报某一段连续的工兵营地一共有多少人,例如Derek问:“Tidy,马上汇报第3个营地到第10个营地共有多少人!”Tidy就要马上开始计算这一段的总人数并汇报。但敌兵营地的人数经常变动,而Derek每次询问的段都不一样,所以Tidy不得不每次都一个一个营地的去数,很快就精疲力尽了,Derek对Tidy的计算速度越来越不满:"你个死肥仔,算得这么慢,我炒你鱿鱼!”Tidy想:“你自己来算算看,这可真是一项累人的工作!我恨不得你炒我鱿鱼呢!”无奈之下,Tidy只好打电话向计算机专家Windbreaker求救,Windbreaker说:“死肥仔,叫你平时做多点acm题和看多点算法书,现在尝到苦果了吧!”Tidy说:"我知错了。。。"但Windbreaker已经挂掉电话了。Tidy很苦恼,这么算他真的会崩溃的,聪明的读者,你能写个程序帮他完成这项工作吗?不过如果你的程序效率不够高的话,Tidy还是会受到Derek的责骂的.
 


Input
第一行一个整数T,表示有T组数据。
每组数据第一行一个正整数N(N<=50000),表示敌人有N个工兵营地,接下来有N个正整数,第i个正整数ai代表第i个工兵营地里开始时有ai个人(1<=ai<=50)。
接下来每行有一条命令,命令有4种形式:
(1) Add i j,i和j为正整数,表示第i个营地增加j个人(j不超过30)
(2)Sub i j ,i和j为正整数,表示第i个营地减少j个人(j不超过30);
(3)Query i j ,i和j为正整数,i<=j,表示询问第i到第j个营地的总人数;
(4)End 表示结束,这条命令在每组数据最后出现;
每组数据最多有40000条命令
 


Output
对第i组数据,首先输出“Case i:”和回车,
对于每个Query询问,输出一个整数并回车,表示询问的段中的总人数,这个数保持在int以内。
 


Sample Input
1 10 1 2 3 4 5 6 7 8 9 10 Query 1 3 Add 3 6 Query 2 7 Sub 10 2 Add 6 3 Query 3 10 End
 


Sample Output
Case 1: 6 33 59
 

这题是zkw线段树中单点修改与区间查询的一般方法:

M的计算 显然最后一行是:

+M:  0 1 2 3....M-1

但是我们求和值是不能求(0,M-1),(zkw线段树不支持首尾查询)

我们查询的应该是开区间(a,b) (这样的目的是保证不出现当前无法判定是否取-

原理:在左边时左边不取,而若右边不为t(s^t≠1),则必取.

    在右边时右边不取,而若左边不为s(s^t≠1),则必取.

建树时要保证n<=M-2

M=1;while (M-2<n) M<<=1;

从C++的角度:

由于char s[]为数组,无法直接比较

需要用 strcmp(string a,string a)==0 判定

它是字符串的cmp 返回字典序比较情况

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<cctype>
#include<iostream>
using namespace std;
#define MAXN (50000+10)
#define MAXAi (50+10)
int n,m,k,M,tt,t[MAXN*5];
char s[50];
int main()
{
//	freopen("Hdu1166.in","r",stdin);
	scanf("%d",&tt);
	for (int k=1;k<=tt;k++)
	{
		printf("Case %d:n",k);
		scanf("%d",&n);
		memset(t,0,sizeof(t));
		M=1;while (M-2<n) M<<=1;
		for (int i=M+1;i<=M+n;i++) scanf("%d",&t[i]);
		for (int i=M;i>=1;i--) t[i]=t[i<<1]+t[(i<<1)^1];


		while (scanf("%s",s)!=EOF)
		{
			if (!strcmp(s,"End")) break;
			int p1,p2;
			scanf("%d%d",&p1,&p2);
			if (s[0]=='Q')
			{
				int ans=0;
				p1--;p2++;p1+=M;p2+=M;
				while (p1^p2^1>0)
				{
					if (~p1&1) ans+=t[p1+1];
					if (p2&1) ans+=t[p2-1];
					p1>>=1;p2>>=1;
				}
				cout<<ans<<endl;
				continue;
			}
			else
			{
				p1+=M;
				if (s[0]=='A') t[p1]+=p2; else t[p1]-=p2;
				for (p1/=2;p1;p1/=2)
				{
					t[p1]=t[p1<<1]+t[(p1<<1)^1];
				}

			}


		}






	}


	return 0;
}


Tyvj Q1024(double的使用)

在C++中 double会以牺牲最小数为代价换取高位

另外请看好题目是求整数部分还是四舍五入

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<cctype>
#include<iostream>
#include<functional>
#include<algorithm>
#include<string>
using namespace std;
#define MAXN (1000+10)
int a[MAXN][MAXN],n;
int main()
{
	long double ans=0.0;
	scanf("%d",&n);
	long long all=0;
	for (int i=1;i<=n;i++)
	{
		for (int j=1;j<=n;j++)
			all+=((long long)n-i+1)*((long long)n-j+1);
	}

	for (int i=1;i<=n;i++)
		for (int j=1;j<=n;j++)
	{
		scanf("%d",&a[i][j]);
		ans+=(long double)(a[i][j])*(long double)(n-i+1)*(long double)(n-j+1)*(long double)(i*j);

	//	cout<<ans<<' ';
	}

	cout.setf(ios::fixed);
	cout.precision(0);
	cout<<trunc(ans/(long double)(all))<<endl;



	return 0;
}

比赛 (long double 与fixed)

比赛

 (mat.pas/c/cpp)

【问题描述】

    有两个队伍A和B,每个队伍都有n个人。这两支队伍之间进行n场1对1比赛,每一场都是由A中的一个选手与B中的一个选手对抗。同一个人不会参加多场比赛,每个人的对手都是随机而等概率的。例如A队有A1和A2两个人,B队有B1和B2两个人,那么(A1 vs B1,A2 vs B2)和(A1 vs B2,A2 vsB1)的概率都是均等的50%。

    每个选手都有一个非负的实力值。如果实力值为X和Y的选手对抗,那么实力值较强的选手所在的队伍将会获得(X-Y)^2的得分。

    求A的得分减B的得分的期望值。

【输入格式】

    第一行一个数n表示两队的人数为n。

    第二行n个数,第i个数A[i]表示队伍A的第i个人的实力值。

    第三行n个数,第i个数B[i]表示队伍B的第i个人的实力值。

【输出格式】

    输出仅包含一个实数表示A期望赢B多少分。答案保留到小数点后一位(注意精度)

【样例输入】

    2

    37

    15

【样例输出】

    20.0

【数据规模】

    对于30%的数据,n≤50。

    对于100%的.据,n≤50000;A[i],B[i]≤50000。

 

∑(a[i]-b[i))^2

注意后缀数要在排序后T_Y

另外C++要用long double ---但是不能用.lf占位符

要用如下的格式

cout.setf(ios::fixed);
	cout.precision(1);



	cout<<ans/n<<endl;

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<cctype>
#include<functional>
#include<algorithm>
#include<iostream>
using namespace std;
#define MAXN (50000+10)
long long n,a[MAXN],b[MAXN],sumb[MAXN],sumb2[MAXN];
int main()
{
    freopen("mat.in","r",stdin);
    freopen("mat.out","w",stdout);

    scanf("%d",&n);
    sumb[0]=sumb2[0]=0;
    for (int i=1;i<=n;i++)
    {
        cin>>a[i];
	}
    sort(a+1,a+1+n);
	for (int i=1;i<=n;i++)
    {
        cin>>b[i];
}
    sort(b+1,b+1+n);

	for (int i=1;i<=n;i++)
	{
		sumb[i]=sumb[i-1]+b[i];
        sumb2[i]=sumb2[i-1]+b[i]*b[i];
	}


	long double ans=0.0;


	for (int i=1;i<=n;i++) cout<<sumb[i]<<' ';
	cout<<endl;
	int r=0;
    for (int i=1;i<=n;i++)
    {
        while (r<n&&a[i]>b[r+1]) r++;


        ans+=a[i]*a[i]*(2*r-n);
        ans+=2*sumb2[r]-sumb2[n];

        ans-=2*a[i]*(2*sumb[r]-sumb[n]);

        /*
		long double tmp=0.0;
        //cout<<r<<endl;

		tmp+=r*a[i]*a[i]-2*a[i]*sumb[r]+sumb2[r];
        cout<<tmp<<endl;

		tmp-=(n-r)*a[i]*a[i]-2*a[i]*(sumb[n]-sumb[r])+sumb2[n]-sumb2[r];
        tmp/=n;

        ans+=tmp;


//		cout<<ans;
	*/
    }

//	cout<<ans<<endl;

	cout.setf(ios::fixed);
	cout.precision(1);



	cout<<ans/n<<endl;



//  while (1);
    return 0;
}

Tyvj P2058(Map)

c++ <map>的使用

其实由于x和y不相等,可以桶排的……

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<cmath>
#include<functional>
#include<algorithm>
#include<map>
using namespace std;
#define MAXN (1000+10)
#define MAXM (1000+10)
struct node
{
	int x,y,w;
	node():x(0),y(0),w(1){}
	node(int _x,int _y,int _w):x(_x),y(_y),w(_w){}

	friend bool operator<(const node a,const node b){ return (a.w!=b.w)?a.w<b.w:a.x+a.y>b.x+b.y;	}
	friend bool operator==(const node a,const node b){ return (a.x==b.x)&&(a.y==b.y);}
}a[MAXN];

int /*hash[MAXN+MAXM][2],*/n,m;
map<node,int> b;
int main()
{
	cin>>n>>m;
	for (int i=1;i<=n;i++)
	{
		scanf("%d%d",&a[i].x,&a[i].y);
		a[i].w=1;
		for (int j=1;j<i;j++)
		{
			if (a[i]==a[j]) a[i].w++;
		}
	}
	sort(a+1,a+1+n);
	for (int i=1;i<=m;i++)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		b[node(x,y,0)]=1;
	}
	for (int i=n;i>=1;i--)
	{
		if (b.find(node(a[i].x,a[i].y,0))==b.end() )
		{
			cout<<a[i].x<<' '<<a[i].y<<endl;
			return 0;


		}
	}




	return 0;
}

ZOJ 2529(不同进制的高精度&sstream)

高精度 a+b

第i位的进制为第 ith 系数

慢慢做吧……

Important---:切记质数表一定要开大一些

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<cctype>
#include<iostream>
#include<functional>
#include<algorithm>
#include<sstream>
using namespace std;
int a[100],siz=0;
char a1[1000],a2[1000];
int A[1000],B[1000],C[1000];
void stod()
{

	istringstream ss(a1);
	int i=1;
	while (ss)
	{
		ss>>A[i];
		i++;
		char c;
		if (ss) ss>>c;
	}
	A[0]=i-1;
	stringstream ss2;
	ss2<<a2;
	i=1;
	while (ss2)
	{
		ss2>>B[i];
		i++;
		char c;
		if (ss2) ss2>>c;
	}
	B[0]=i-1;
	for (int i=1;i<=(A[0]>>1);i++) swap(A[i],A[A[0]-i+1]);
	for (int i=1;i<=(B[0]>>1);i++) swap(B[i],B[B[0]-i+1]);

}
int main()
{
	for (int i=1;siz<=80;i++)
	{
		bool flag=0;
		for (int j=2;j<=i-1;j++)
			if (i%j==0) flag=1;
		if (!flag)
		{
			siz++;
			a[siz]=i;
		}
	}
//	for (int i=1;i<=25;i++) cout<<a[i]<<' ';
	while (scanf("%s%s",a1,a2)!=EOF)
	{
		memset(A,0,sizeof(A));
		memset(B,0,sizeof(B));
		stod();
//		for (int i=1;i<=B[0];i++) cout<<B[i]<<' ';
		memset(C,0,sizeof(C));
		C[0]=max(A[0],B[0])+1;
		for (int i=1;i<=C[0];i++)
		{
			C[i]+=A[i]+B[i];
			C[i+1]+=C[i]/a[i+1];
			C[i]%=a[i+1];
		}
		while (!C[C[0]]) C[0]--;
		for (int i=C[0];i>=2;i--) cout<<C[i]<<",";
		cout<<C[1]<<endl;
	}
//	while (1);
	return 0;
}

Tyvj P2053(线段覆盖‘s精度误差&析构函数)

众所周知,精度误差是很坑人的东西

而且有的时候有了eps反而会错(考虑你的条件是严苛还是放宽)

从 0 到  x0 的覆盖中,点的排序就是一例

首先要尽可能以x排序,然后左端点尽量靠右

但是左端点会爆误差……所以先考虑 端点的误差是否可以忽略,如果不行就算相等)

第二处是排序的对象

理论上是从0到x0 不合条件的都被赋0了……

但是 有可能出现 0<x0<a[i].x<a[i+7].x这样的 整条线段不在里面的情况 此时若用max min 那么 会忽略左端点 (我们的本意是让不在区间内的点的区间删了-要删就全删)

故 需考虑·这样的情况

 <-最右边的黄色和青色的

第三处是答案(终极精度误差)   你要让最左端点<eps和最右端点<x0-eps 这里的限制应为严苛(倘若放宽,最左端点为0(前面已经让它∈[0.x0])都不行的话  会出现永远不可能的情况 


#include<iostream>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<functional>
#include<algorithm>
using namespace std;
#define MAXX (10000+10)
#define MAXH (100+10)
#define MAXN (2*7+10)
double h,x0,m;
const double eps=1e-10;
bool cmp(const double a,const double b);
bool equal(const double a,const double b)
{
	if (-eps<a-b&&a-b<eps) return 1;
	else return 0;
}
struct node  //表示线段端点 y=1表示左端点 y=-1有端点
{
	double x,y;
	node():x(0.0),y(0.0){}
	node(double _x,double _y):x(_x),y(_y){}
	friend bool operator<(const node a,const node b){return equal(a.x,b.x)?a.y>b.y:cmp(a.x,b.x);/*(a.y!=b.y)?a.y>b.y:a.x+eps<b.x||a.x-eps<b.x;*/ /* ? */	}
}a[MAXN];
double x[MAXN],r[MAXN];
bool cmp(const double a,const double b)
{
//	cout<<(a-eps<b)<<endl;
	return ((a-eps<b)||(a+eps<b));
}
bool is_ok(double m)
{
	for (int i=1;i<=7;i++)
	{
		if (h<=r[i]+m)
		{
			double dis=sqrt(pow((r[i]+m),2)-pow((h),2));
		//	if (dis<0) cout<<dis<<' ';
			a[i].x=max(0.0,x[i]-dis);a[i+7].x=min(x0,x[i]+dis);
		//	if (max(0.0,x[i]-dis)>min(x0,x[i]+dis)) cout<<x[i]-dis<<' '<<x[i]+dis;

		}
		else a[i].x=a[i+7].x=0;
		if (a[i].x>a[i+7].x) a[i].x=a[i+7].x=0;
		a[i].y=1;a[i+7].y=-1;
	}
//	for (int i=1;i<=14;i++) cout<<a[i].x<<' '<<a[i].y<<endl;
	sort(a+1,a+1+14);
//	for (int i=1;i<=14;i++) cout<<a[i].x<<' '<<a[i].y<<endl;

	for (int i=1,j=0;i<14;i++)
	{
		j+=a[i].y;
		if (!j) return 0;
	}
//	if (cmp(0.0,a[1].x)||cmp(a[14].x,x0)) return 0;
	if ((eps<a[1].x)||(a[14].x<x0-eps)) return 0;
	return 1;
}
int main()
{
//	freopen("rainbow.in","r",stdin);
	scanf("%lf%lf",&h,&x0);
	for (int i=1;i<=7;i++) scanf("%lf%lf",&x[i],&r[i]);

//	for (int i=1;i<=7;i++) cout<<r[i]<<' ';

/*	node a=node(3.0,-1.0);
	node b=node(2.0,-1.0);
	cout<<(a<b)<<endl;
*/
	double l=0.0,r=x0+h+1;
//	cout<<is_ok(60.0);
	while (r-l>eps)
	{
		double m=(l+r)/2;
		if (is_ok(m)) r=m;
		else l=m;
	}
	printf("%.2lfn",r);

//	while (1);
	return 0;
} 



高级打字机 (Tries)

Problem 1 高级打字机(type.cpp/c/pas)

【题目描述】

早苗入手了最新的高级打字机。最新款自然有着与以往不同的功能,那就是它具备撤销功能,厉害吧。

请为这种高级打字机设计一个程序,支持如下3种操作:

1.T x:在文章末尾打下一个小写字母x。(type操作)

2.U x:撤销最后的x次修改操作。(Undo操作)

(注意Query操作并不算修改操作)

3.Q x:询问当前文章中第x个字母并输出。(Query操作)

文章一开始可以视为空串。

 

【输入格式】

第1行:一个整数n,表示操作数量。

以下n行,每行一个命令。保证输入的命令合法。

 

【输出格式】

每行输出一个字母,表示Query操作的答案。

 

【样例输入】

7

T a

T b

T c

Q 2

U 2

T c

Q 2

【样例输出】

b

c

【数据范围】

对于40%的数据 n<=200;

对于100%的数据 n<=100000;保证Undo操作不会撤销Undo操作。

<高级挑战>

对于200%的数据 n<=100000;Undo操作可以撤销Undo操作。

<IOI挑战>

必须使用在线算法完成该题。

这题要用字典树(Tries)

还有msm(倍增算法)

另外 补充一点

char  s[0]   或者 char 

scanf("%s",s)

 这句会存不下""

因此会把正在循环的自变量i 变成 0

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<cmath>
#include<vector>
#include<cctype>
using namespace std;
#define MAXN (100000+10)
#define LOGMAXN (16+10)
int n,tot=0;
struct Tnode
{
	int deep,f[LOGMAXN];
	char edge;
	Tnode()
	{
		memset(f,0,sizeof(f));
		deep=-1;
		edge='';
	}
	Tnode(char _edge,int _fa,int _deep)
	{
		memset(f,0,sizeof(f));
		f[0]=_fa;
		edge=_edge;
		deep=_deep;
	}
	int logdeep()
	{
		return int(trunc(log(deep)/log(2)));
	}
}node[MAXN];
int log2(int a)
{
	return int(trunc(log(a)/log(2)));
}
void msm(Tnode &a)
{
	int n=a.logdeep();
//	if (n==1) return;
	for (int i=1;i<=n;i++)
	{
		a.f[i]=node[a.f[i-1]].f[i-1];
	}
}
void type()
{
	char c;
	scanf("%s",&c);
	tot++;
	node[tot]=Tnode(c,tot-1,node[tot-1].deep+1);
	msm(node[tot]);
}

void quere()
{
	int p;
	scanf("%d",&p);
	Tnode now=node[tot];
	p=now.deep+1-p; //第i's 祖先
	while (p)
	{
		int i=log2(p);
		p-=(1<<i);
		now=node[now.f[i]];

	}
	printf("%cn",now.edge);

}
void undo()
{
	int p;
	scanf("%d",&p);
	tot++;
	node[tot]=node[tot-1-p];
}
int main()
{
	freopen("type.in","r",stdin);
	freopen("type.out","w",stdout);
	scanf("%d",&n);
	node[0]=Tnode();
	for (int ii=1;ii<=n;ii++)
	{
//		printf("%dn",ii);
		char s[10];
//		printf("%dn",ii);
		scanf("%s",s);
//		printf("%dn",ii);
//		while(1);
		switch(s[0])
		{
			case 'T':type();break;
			case 'U':undo();break;
			case 'Q':quere();break;
		}


	}
//	while (1);
	return 0;
}

求和式 (C++ 坑爹的<<,>>,%lld)

求和式(x3)

题目描述

作为本场考试的第一题,你的任务十分简单:

给定长度为n的序列A[i],求所有A[i]xor A[j] (i<j)的值之和

 

输入

第一行一个整数N

接下来N行,第i行为A[i]

输出

所需的值

 

样例输入

3

7

3

5

样例输出

12

样例解释

7 xor 3+3 xor 5+7 xor 5 = 4+6+2 = 12

 

数据范围

对于40%的数据,N<=5000

对于100%的数据,N<=1000000

c++中的%lld千万别用啊 ,各种坑人!

统一用cout 

另外C++中(long long)(1<<k)

这里要转,不然必wa

千万要先乘,和别的数乘完不定什么数了……

本题是位运算分解成一位一位运算(重要性质)

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<functional>
#include<algorithm>
using namespace std;
#define MAXN (100+10)
int n,a,c[MAXN][2]={0};// 1<<i =(0.1)
int main()
{
	freopen("x3.in","r",stdin);
	freopen("x3.out","w",stdout);

/*	for (int i=0;i<=100;i++)
	{
		cout<<c[i][0]<<' '<<c[i][1]<<endl;
	}
*/	long long ans=0;
	scanf("%d",&n);
	int len=0;
	for (int i=1;i<=n;i++)
	{
		scanf("%d",&a);
		int tot=-1;
		int j=100;
		while (j--) {c[++tot][a%2]++;a/=2;}



		len=len<tot?tot:len;

	}
/*	for (int i=0;i<=100;i++)
	{
		cout<<c[i][0]<<' '<<c[i][1]<<endl;
	}
*/
	for (int i=0;i<=28;i++)
	{
		ans+=(long long)(1<<i)*(long long)c[i][1]*(long long)(n-c[i][1]);

//	cout<<ans<<endl;
	}


/*
	for (int i=0;i<=len;i++) cout<<c[i][0]<<' '<<c[i][1]<<' '<<endl;
*/

//	printf("%lldn",ans);
	cout<<ans<<endl;
//	while (1);

	return 0;
}