C++中如何实现函数任意长参数。。。

额。。这是一篇有点无聊+SB的文章。。神牛可以无视囧。。。
恩。。比如说你在Dp或者XX的时候。。需要一些个数的最大值,
手动比较和用max都很麻烦的话。。可以考虑用这个可变长形参。。
inline int max(int n,…)
{
va_list ap;
va_start(ap,n);
int ret=-inf,i,x;
rep(i,n){x=va_arg(ap,int);if(x>ret)ret=x;}
va_end(ap);
return ret;
}
然后就可以这么调用了。。
max(3,1,9,8);看上去远没有Java的爽囧。。不过凑合凑合吧。。
va_list是一个预先定义的数据结构,用来储存参数列表的。
va_start就是把参数放到va_list里面去,后面还要跟个n表示参数的个数。。
va_arg(ap,int)每次取出下一个参数,还要指定类型。。
最后一个va_end(ap)表示清空这个,回收内存。。。

还有在#define里面也有这样的用法类似的。。
#define rep(i,n) for(i=0;i<n;i++)
#define SC(…) scanf(__VA_ARGS__)
#define PR(…) printf(__VA_ARGS__)
int main()
{
int x;
SC("%d",&x);
PR("%d",x);
}

快速IO in C++

作为一个使用C++的童鞋。。。龟速的IO往往令人蛋疼。。所以要手动加速。。
(1):cin : scanf = 10 : 1
cin的龟速是闻名的。。。只要输入超过1W个数我就不敢用了。。
(2):
看看下面这个函数:
inline int nextInt()
{
char c;c=getchar();
while(c!=’-‘&&(c<‘0’||c>’9′))c=getchar();
int n=0,s=1;if(c==’-‘)s=-1,c=getchar();
while(c>=’0’&&c<=’9′)n*=10,n+=c-‘0′,c=getchar();
return n*s;
}很显然这是一个很SB的读入数字的函数。。。
但是这个的速度是scanf的4倍瀑布汗。。
(3):Pascal的读入之所以快速是因为里面有读入到缓冲区。。
C++只好手动了。。
#define BUFSIZE 1000000
char buf[BUFSIZE], *pt = buf + BUFSIZE, *pend = buf + BUFSIZE;
int sign;
#define read()
do{
if (pt >= pend)
{
pt = buf;
fread(buf, 1, BUFSIZE, stdin);
}
} while(0)

#define scan(t)
{
t = 0;sign=1;
read();
while ((*pt<‘0’||*pt>’9′)&&*pt!=’-‘) {pt ++; read();}
if(*pt==’-‘)sign=-1,pt++;
while (((*pt) >= ‘0’ && (*pt) <= ‘9’)) {t = t * 10 + (*(pt ++)) – ‘0’; read();}
t*=sign;
}
#define scan_str(s)
{
int p = 0;
read();
while ((*pt) == ‘ ‘ || (*pt) == ‘n’ || (*pt) == ‘r’) {pt ++; read();}
while (!((*pt) == ‘ ‘ || (*pt) == ‘n’ || (*pt) == ‘n’)) {s[p ++] = (*(pt ++)); read();}
s[p] = 0;
}fread就是直接读一大块数据。。速度自然很快。。然后手动模拟缓冲区。。
速度又提高一倍。。跟Pascal差不多了。。
(5):输出也有悲剧的地方。。
int A[20],k;
inline void print_int(int x)
{
if(x<0)putchar(‘-‘),x=-x;
k=0;while(x)A[k++]=x%10,x/=10;
for(int i=k-1;i>=0;i–)putchar(‘0’+A[i]);
putchar(‘n’);
}这么一个函数往往比纯printf快N多。。。
(6):或者干脆输出也用一个缓冲区。。
用一个大数组s存储要输出的字符。。然后一口气输出。。。

【转】追MM算法(转)

动态规划
你追一个MM的时候,需要对该MM身边的各闺中密友都好,这样你追MM这个问题就分解为对其MM朋友的问题,只有把这些问题都解决了,最终你才能追到MM。

该方法适用于聪明的MM,懂得“看一个人,不是看他如何对你,而是看他如何对他人。”的道理,并且对付这样的MM总能得到最优解。

该方法的缺点是开销较大,因为每个子问题都要好好对待。。。。
——————————————————————–

贪心法
你追一个MM的时候,从相识到相知,每次都采用最aggressive的方式,进攻进攻再进攻!从不采用迂回战术或是欲擒故纵之法!目标是以最快的速度确立两人关系。
该法优点是代价小,速度快,但缺点是不是每次都能得到最优解。。。。。
——————————————————————–

回溯算法
追一个MM,但也许你还是情窦初开的新手,不知道如何才能讨得MM的欢心,于是你只好一条路一条路的试,MM不开心了,你就回溯回去换另一种方式。当然其 间你也许会从某些途径得到一些经验,能够判断哪些路径不好,会剪枝(这就是分支估界了)。你也可以随机选择一些路径来实施,说不定能立杆见影(这就是回溯 的优化了)但总的来说,你都需要一场持久战。。。。
该算法一般也能得到最优解,因为大多数MM会感动滴!!但其缺点是开销大!除非你是非要谈一场恋爱不可,否则不推荐使用。特别是你可能还有许多其他的事情要做,比如学习,比如事业。。。。
——————————————————————–

NP完全问题
呵呵,那你为什么那么贱,非要去追呢?记住:“天涯何处无芳草!” 不过如果你“非如此不可”的话,建议升级你的硬件,好好学习,好好工作,加强实力,人到中年的时候也许你能解开NP难。。。。

补充NP:在你追了若干美女都失败告终后,你发现有一批美女追起来是一样困难的,如果你能追到其中任何一个就能追到其他所有的美女,你把这样的女人叫作NP-Complete。
P=NP:这是一个美好的猜想,追美女和恐龙的难度其实一样。
APX与Random:NP的美女难追,你无法完全占有她。你只好随机的去靠近她,装作若无其事;或者用一种策略,追到她的一个approximation ratio,例如50%。
APX-hard:这样的女人,连一个固定的百分比都不给你,还是另谋高就吧。
////////////////////////////////////////////////////////////////////

深度优先和广度优先:
深度优先就是追一个mm追到底,直到失败然后换个mm继续追……
广度优先就是同时追多个mm,一起发展……
////////////////////////////////////////////////////////////////////

二叉树的前序、中序和后序遍历:
前序就是直接搞定MM,然后搞定她爸妈(左)和你自己爸妈(右)
中序就是先搞定未来岳父岳父,然后搞定她,最后告诉你爸妈
后续就是,让未来的岳父岳母和自己爸妈都觉得你们合适之后,才对MM下手,这个时候就没有障碍了啊
////////////////////////////////////////////////////////////////////

网络流
追MM的时候总避免不了送礼物,但是你老是直接送礼物就会给MM造成很大的压力,于是你就想到了通过朋友来转送的方法。你希望送给MM尽可能多的礼 物,所以就是需要找到一中配送方案,就是最大流了。然而你请别人帮忙并不是不要开销的,你让A同学拿去给B同学可能需要一些花费,自然你不是一个大款,想 最小化这个花费,那么就是最小费用最大流了……

SGU 311. Ice-cream Tycoon

311. Ice-cream TycoonTime limit per test: 3 second(s)
Memory limit: 65536 kilobytesinput: standard
output: standard

You’ve recently started an ice-cream business in a local school. During a day you have many suppliers delivering the ice-cream for you, and many students buying it from you. You are not allowed to set the prices, as you are told the price for each piece of ice-cream by the suppliers.

The day is described with a sequence of queries. Each query can be eitherARRIVE n c, meaning that a supplier has delivered n pieces of ice-cream pricedc each to you, or BUY n t, meaning that a student wants to buy n pieces of ice-cream, having a total of t money. The latter is processed as follows: in casen cheapest pieces of ice-cream you have cost no more than t (together), you sell those n cheapest pieces to the student; in case they cost more, she gets nothing. You start the day with no ice-cream.

For each student, output HAPPY if she gets her ice-cream, and UNHAPPYif she doesn’t.

InputThe input file contains between 1 and 105 queries (inclusive), each on a separate line. The queries are formatted as described above, either ARRIVE n cor BUY n t, 1 ≤ nc ≤ 106, 1 ≤ t ≤ 1012.

OutputFor each BUY-query output one line, containing either the word HAPPY or the word UNHAPPY (answers should be in the same order as the corresponding queries).

Example(s) sample input sample output ARRIVE 1 1
ARRIVE 10 200
BUY 5 900
BUY 5 900
BUY 5 1000 HAPPY
UNHAPPY
HAPPY
这个题目一看就是裸的线段树囧。。就是老TLE瀑布汗。。。这次我火了。。写了个带标记的非递归
线段树终于A了内流满面囧。。。
Code:
#include <vector>
#include <algorithm>
#include <utility>
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <time.h>
#define rep(i,n) for(int i=0;i<n;i++)
#define pb push_back
#define Debug(x) cout<<#x<<"="<<x<<endl;
#define For(i,l,r) for(int i=l;i<=r;i++)
#define tr(e,x) for(typeof(x.begin()) e=x.begin();e!=x.end();e++)
#define printTime cout<<"Time:"<<pre-clock()<<endl;pre=clock();
const int inf=~0U>>1,maxc=1<<20;
using namespace std;
typedef long long ll;
char cmd[100];
#define scan(t)
{
char pt;
while(pt=getchar(),pt<‘0’||pt>’9′);
t=pt-‘0′;
while(pt=getchar(),pt>=’0’&&pt<=’9′)t=t*10+pt-‘0′;
}
bool Mark[1<<21];
ll sum[1<<21]={},num[1<<21]={};
void set(int t)
{
sum[t]=sum[t*2]+sum[t*2+1];
num[t]=num[t*2]+num[t*2+1];
}
void MarkIt(int t)
{
sum[t]=num[t]=0;
Mark[t]=true;
}
void PushDown(int t)
{
if(Mark[t])
MarkIt(t*2),MarkIt(t*2+1);
Mark[t]=false;
}
void Update(int t,ll c)
{
int i,l,r;
for(i=1,l=0,r=maxc;i<maxc;)
{
PushDown(i);i<<=1;
int m=l+r>>1;
if(t>=m)i++,l=m;
else r=m;
}
i=t+maxc;sum[i]+=t*c;num[i]+=c;
for(i>>=1;i;i>>=1)set(i);
}
ll get(int n)
{
if(num[1]<n)return -1;
ll ret=0;int i;
for(i=1;i<maxc;)
{
PushDown(i);i<<=1;
if(num[i]>=n)continue;
ret+=sum[i];n-=num[i];i++;
}
return ll(n)*(i-maxc)+ret;
}
void clear(int n)
{
int i;
for(i=1;i<maxc;)
{
PushDown(i);i<<=1;
if(num[i]>=n)continue;
n-=num[i];MarkIt(i);i++;
}
Update(i-maxc,-n);
}
int main()
{
//freopen("in","r",stdin);
int n;ll c;
while(scanf("%s",cmd)==1)
{
scan(n);scan(c);
if(cmd[0]==’A’)Update(c,n);
else
{
ll tmp=get(n);
if(tmp==-1||tmp>c)
puts("UNHAPPY");
else
puts("HAPPY"),clear(n);
}
}
}

[Zjoi2004]Lunch 午餐

[Zjoi2004]Lunch 午餐

Time Limit:3000MS  Memory Limit:65536K
Total Submit:13 Accepted:9
Case Time Limit:1000MS

Description

上午的训练结束了,THU ACM小组集体去吃午餐,他们一行N人来到了著名的十食堂。这里有两个打饭的窗口,每个窗口同一时刻只能给一个人打饭。由于每个人的口味(以及胃口)不 同,所以他们要吃的菜各有不同,打饭所要花费的时间是因人而异的。另外每个人吃饭的速度也不尽相同,所以吃饭花费的时间也是可能有所不同的。
THU ACM小组的吃饭计划是这样的:先把所有的人分成两队,并安排好每队中各人的排列顺序,然后一号队伍到一号窗口去排队打饭,二号队伍到二号窗口去排队打 饭。每个人打完饭后立刻开始吃,所有人都吃完饭后立刻集合去六教地下室进行下午的训练。
现在给定了每个人的打饭时间和吃饭时间,要求安排一种最佳的分队和排队方案使得所有人都吃完饭的时间尽量早。
假设THU ACM小组在时刻0到达十食堂,而且食堂里面没有其他吃饭的同学(只有打饭的师傅)。每个人必须而且只能被分在一个队伍里。两个窗口是并行操作互不影响 的,而且每个人打饭的时间是和窗口无关的,打完饭之后立刻就开始吃饭,中间没有延迟。
现在给定N个人各自的打饭时间和吃饭时间,要求输出最佳方案下所有人吃完饭的时刻。

Input

第一行一个整数N,代表总共有N个人。
以下N行,每行两个整数 Ai,Bi。依次代表第i个人的打饭时间和吃饭时间。

Output

一个整数T,代表所有人吃完饭的最早时刻。

Sample Input

5
2 2
7 7
1 3
6 4
8 5

Sample Output

17

Hint

方案如下:

窗口1: 窗口2:
7 7 1 3
6 4 8 5
2 2

【限制】
所有输入数据均为不超过200的正整数。

Source

额。这个题目还不错。。挺有意思的。。
首先一看到这经典的模型,可以B大的要在前面。。
然后就可以动归了。。
先按B降序排序。。
用Dp[i][j]表示前i个,第一个队的吃饭时间和为j的最优值。。
Code:
#include <vector>
#include <algorithm>
#include <utility>
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <set>
#include <map>
#include <cstring>
#include <time.h>
#define rep(i,n) for(int i=0;i<n;i++)
const int inf=~0U>>1,maxn=201;
using namespace std;
int A[maxn],B[maxn],P[maxn],n;
bool cmp(int i,int j)
{
return B[i]>B[j];
}
int Dp[2][maxn*maxn];
inline void Update(int&t,int c)
{
if(t==-1||t>c)t=c;
}
int main()
{
//freopen("in","r",stdin);
cin>>n;
rep(i,n)
{
cin>>A[i]>>B[i];
P[i]=i;
}
sort(P,P+n,cmp);
int now=0,next=1,sum=0;
memset(Dp[next],-1,sizeof Dp[next]);
Dp[next][0]=0;
for(int i=0;i<n;i++)
{
int t=P[i],c,first,second,nc;
swap(now,next);
memset(Dp[next],-1,sizeof Dp[next]);
rep(j,sum+1)
if((c=Dp[now][j])!=-1)
{
first=j;
second=sum-j;
//Put it In First Queue
nc=max(first+A[t]+B[t],c);
Update(Dp[next][j+A[t]],nc);
//Put it In Second Queue
nc=max(second+A[t]+B[t],c);
Update(Dp[next][j],nc);
}
sum+=A[t];
}
int ans=inf;
rep(i,sum+1)if(Dp[next][i]!=-1)ans=min(ans,Dp[next][i]);
cout<<ans<<endl;
}

[Zjoi2006]trouble 皇帝的烦恼

[Zjoi2006]trouble 皇帝的烦恼

Time Limit:1000MS  Memory Limit:65536K
Total Submit:54 Accepted:20

Description

经过多年的杀戮,秦皇终于统一了中国。为了抵御外来的侵略,他准备在国土边境安置n名将军。
不幸的是这n名将军羽翼渐丰,开始展露他们的狼子野心了。他们拒绝述职、拒绝接受皇帝的圣旨。秦皇已经准备好了秘密处决这些无礼的边防大将。不过 为防兵变,他决定先授予这些将军一些勋章,为自己赢得战略时间。
将军们听说他们即将被授予勋章都很开心,他们纷纷上书表示感谢。第i个将军要求得到ai枚不同颜色的勋章。但是这些将军都很傲气,如果两个相邻的 将军拥有颜色相同的勋章他们就会认为皇帝不尊重他们,会立即造反(编号为i的将军和编号为i+1的将军相邻;因为他们驻扎的边境可以类似看成一个圆形,所 以编号1和编号n的将军也相邻)。
皇帝不得不满足每个将军的要求,但对他们的飞扬跋扈感到很气愤。于是皇帝决定铸造尽量少种类的勋章来满足这些狂妄者的要求。请问他至少要铸造多少 种颜色的勋章?

Input

第一行有一个整数n(1<=n<=20000)。
接下来n行每行一个整数ai,表示第i个将军要求得到多少种勋章。(1<=ai<=100000)

输出一个整数,即最少需要多少种勋章。

Output

4
2
2
1
1

Sample Input

4

Sample Output

Source

Day2
靠。。这道破题让我WAN次。。真是悲剧。。看来太不细心了囧。。。
首先这个题目很显然如果扫描的话,由于是环形的,可以把奖章看成两种,
第一种属于第一个人的,第二种是不属于的。
那么如果Dp的话要记录种数,显然要TLE。。
所以要二分答案。。
然后可以发现每个人能拿的第一种奖章数是一个区间。。
假设第i个人的区间是l,r
那么列出一系列条件(这点一定要考虑周全,不然WA)。。
算出第i+1个人的区间,然后看看第N个人的区间是否包含0。。
Code:

#include <cstdio>
#include <iostream>
#define rep(i,n) for(int i=0;i<n;i++)
const int maxn=20000,inf=~0U>>1;
using namespace std;
int a[maxn],n,l[maxn],r[maxn];
inline void checkmin(int&x,int c){if(x>c)x=c;}
inline void checkmax(int&x,int c){if(x<c)x=c;}
bool Check(int K)
{
l[0]=r[0]=a[0];
for(int i=1;i<n;i++)
{
l[i]=-inf;r[i]=inf;
if(a[i-1]+a[i]>K)return false;
checkmin(r[i],a[0]-l[i-1]);
checkmin(r[i],a[0]);
checkmin(r[i],a[i]);
checkmax(l[i],a[0]+a[i-1]+a[i]-K-r[i-1]);
checkmax(l[i],a[i]-K+a[0]);
checkmax(l[i],0);
if(l[i]>r[i])return false;
}
return l[n-1]<=0;
}
int main()
{
//freopen("in","r",stdin);
scanf("%d",&n);rep(i,n)scanf("%d",a+i);
int l=0,r=500000;
while(l+1<r)
{
int m=l+r>>1;
if(Check(m))r=m;else l=m;
}
printf("%dn",r);
}

Baltic OI 2010

额。。前几天花了点时间A光了Baltic OI 2010的题目。。感觉还是挺有意思的。。
就写个小结吧囧(其实是充数的,官网上有题解的囧。。)。。。
[Baltic2010]Bears
这个题目的二分还是不难想的囧。。假如二分一下可以阻拦在外的长度的话,
一开始禁止区域是个正方形,然后如果有mainstreet伸入里面的话,这些
mainstreet上面的点自然也划入禁止区域,然后注意到如果一个点有两个
方向上都是禁止区域的点的话,那么这个点就可以无压力进入禁止区域,
故其也是禁止区域。。所以禁止区域一定是个矩形。。
然后看就二分+判断(A,B)是否在里面就可以了。。
[Baltic2010]lego
这个题目首先可以发现状态数肯定不会大,然后对于某一个状态首先要符合
输入的条件,如果有些没被看到的话,可以随便染。。
那么似乎好像就可以状态压缩Dp了。。由于每次都要能够放在上一个的上面,
所以要记录当前的层数和最上面一个是什么。。
常数有点小重要,TLE了一次囧。。
[Baltic2010]Pcb
首先按X1排序。。那么找一条最长的递减的链L,显然这个
链上两两不能分在一层,所以最少要|L|的层数,可证这是可行的囧。。
[Baltic2010]Bins
额。。这个题目有点猥琐。。他的意思就是每个数只能跟比它大的数配对,
问前X个跟第X+1..2X个之间能够完全匹配的最大的X是多少。。
设A[t]为前面X个中大于t的数有几个,
B[t]为X+1…2X中大于t的数有几个。。
显然大于t的数只能用大于t+1的数来放,
所以A[t]<=B[t+1]。。用归纳法可以证明这个。。
然后为了判断是否成立,
假设C[t]是前X中t的个数,D[t]是X+1..2X中t+1的个数。。
那么设E[t]=C[t]-D[t]。。可以发现A[t]-B[t+1]的最大值就是E[t]的最大后缀。。
所以使用线段树维护这个就可以了。。每次修改都是O(LogN)的。。
[Baltic2010]candies
额。。这个题目非常的强大。。
首先可以把题目变换一下,变成删掉一个,再添加一个。。
注意如果添加的话,我可以弄一个很大的能弄出的种数*2.。
所以就变成了对每一个,看它删掉之后的种数,找一个最大的。。
首先注意到一般的Dp是这样的
Dp[i][j]=Dp[i-1][j]+Dp[i-1][j-A[i]]…
那么由于物品是对称的,每个都可以看成最后一个,所以
Dp[i-1][j]=Dp[i][j]-Dp[i-1][j-A[i]]…
这样的话对每个物品就可以在O(B)的时间搞出它能弄出来的种数了。。
然后这部分的复杂度就是O(N*B)。。
不过有一点就是显然会溢出,不过也没事,我们只要判是否0就可以了。。
随便找个数mod一下就差不多了。。

第二步就是要找一个最小的数+进去,使得种数*2,
注意到这个数不能是任何两个不相交子集的差,
也就是说不能用A[0],-A[0],A[1],-A[1]….表示出来。。
对这些数用Dp就可以了。。。

[ZJOI2009]染色游戏

[ZJOI2009]染色游戏

Time Limit:5000MS  Memory Limit:65536K
Total Submit:22 Accepted:13
Case Time Limit:1000MS

Description

一共n × m 个硬币,摆成n × m 的长方形。dongdong 和xixi 玩一个游戏,
每次可以选择一个连通块,并把其中的硬币全部翻转,但是需要满足存在一个
硬币属于这个连通块并且所有其他硬币都在它的左上方(可以正左方也可以正
上方),并且这个硬币是从反面向上翻成正面向上。dongdong 和xixi 轮流操作。
如果某一方无法操作,那么他(她) 就输了。dongdong 先进行第一步操作,假
设双方都采用最优策略。问dongdong 是否有必胜策略。

Input

第一行一个数T,表示他们一共玩T 局游戏。接下来是T 组游戏描述。每
组游戏第一行两个数n;m,接下来n 行每行m 个字符,第i 行第j 个字符如
果是“H” 表示第i 行第j 列的硬币是正面向上,否则是反面向上。第i 行j 列
的左上方是指行不超过i 并且列不超过j 的区域。

Output

对于每局游戏,输出一行。如果dongdong 存在必胜策略则输出“- -”(不含
引号) 否则输出“= =”(不含引号)。(注意输出的都是半角符号,即三个符号
ASCII 码分别为45,61,95)

Sample Input

32
3
HHH
HHH
2 3
HHH
TTH
2 1
T
H

Sample Output

= =
– –
– –

Hint

对于40% 的数据,满足1 ≤ n;m ≤ 5。
对于100% 的数据,满足1 ≤ n;m ≤ 100,1 ≤ T ≤ 50。

Source
这个题目一看就知道是要算SG函数的破题。。很多年
以前我看到这题就哆嗦囧。。不过今天研究了一个晚上
各种文献算是会做了瀑布汗。。。
首先肯定是要算SG函数值的,设点(x,y)的函数值为F(x,y)
先证个好证的:
当x和y都大于0的时候,F(x,y)=2^(x+y)..
终态就是没有一个T囧。。SG(终态)=0
首先使用归纳法,为了方便吧(0,0),(0,1),(1,0)也考虑进去,
这些点显然满足条件。。
然后开始用x+y=k,按k归纳。。
假设k-1没问题了。。
那么要证明k的话,就要证明以(x,y)为最右下的有联通块的SG值为0..2^(x+y)-1,且没有2^(x+y)。。
后者是显然的,因为(x,y)是最右下,所以其它的点在x+y这位上都是0。。怎么也不会弄出个2^(x+y)。
前者也可以构造出来。。具体的说就是给定个数X,如果它在第i位上是0,那么我就在x+y=i那条线上弄两个点,否则就弄一个。。YY一下就可以了。。
再证个麻烦的。。
当x=0或y=0的时候,显然上面对证法就不能成立囧。。
但此时已经变成一个经典的一维问题了,决策也是O(N)
的。。所以弄个N^2的Dp算下SG值就可以了。。
不过还是讲一下更加数学化的做法吧,
这个问题叫Ruler游戏。。
就是给你一条硬币,每次翻连续的一段,最后一个一定是由
反面到正面。。
设F(x)为第x个硬币的SG值。。
那么可以证明F(x)为可以将x整除的2的最大幂。。
用归纳法搞一下就可以了。。。
话说这个题目真TMD猥琐。。输出不对的。。
看哪个ASCII的号码的话应该是=_=he-_-才对啊囧。。。
Code:

#include <cstdio>
#include <cstring>
#define rep(i,n) for(int i=0;i<n;i++)
const int inf=~0U>>1,maxn=105;
using namespace std;
inline int lowbit(int x){return x&-x;}
int log(int x){return x==1?0:(log(x/2)+1);}
int n,m;
int sg(int x,int y)
{
if(x==0||y==0)return log(lowbit(x+y+1));
return x+y;
}
bool E[maxn*2]={};
int main()
{
//freopen("in","r",stdin);
int T;scanf("%d",&T);
rep(t,T)
{
scanf("%d%d",&n,&m);
memset(E,0,sizeof E);
rep(i,n)
{
scanf(" ");
rep(j,m)
{
char c=getchar();
if(c==’T’)
E[sg(i,j)]^=1;
}
}
bool ok=true;
rep(i,n+m)if(E[i]){ok=false;break;}
if(ok)puts("=_=");
else puts("-_-");
}
}

[JSOI2008]球形空间产生器sphere

[JSOI2008]球形空间产生器sphere

Time Limit:1000MS  Memory Limit:165536K
Total Submit:147 Accepted:89

Description

有一个球形空间产生器能够在n维空间中产生一个坚硬的球体。现在,你被困在了这个n维球体中,你只知道球面上n+1个点的坐标,你需要以最快的速度确定这 个n维球体的球心坐标,以便于摧毁这个球形空间产生器。

Input

第一行是一个整数,n。
接下来的n+1行,每行有n个实数,表示球面上一点的n维坐标。每一个实数精确到小数点后6位,且其绝对值都不超过20000。

Output

有且只有一行,依次给出球心的n维坐标(n个实数),两个实数之间用一个空格隔开。每个实数精确到小数点后3位。数据保证有解。你的答案必须和标准输出一 模一样才能够得分。

Sample Input

2
0.0 0.0
-1.0 1.0
1.0 0.0

Sample Output

0.500 1.500

数据规模:
对于40%的数据,1<=n<=3
对于100%的数据,1<=n<=10
提示:给出两个定义:
1、 球心:到球面上任意一点距离都相等的点。
2、 距离:设两个n为空间上的点A, B的坐标为(a1, a2, …, an), (b1, b2, …, bn),则AB的距离定义为:dist = sqrt( (a1-b1)^2 + (a2-b2)^2 + … + (an-bn)^2 )

Source
额。。曾经我非常执着的一定要用模拟退火A这个题目。。
没成功过。。。今天看到这个没过觉得很碍眼。。于是写
了个解方程囧。。。。
额。。实际上这个题目只要在N+1个点中每相邻两个点间
做个平分线。。那么很显然球心就是N个平分线的交点,
这个解方程就OK了瀑布汗。。。
Code:
#include <vector>
#include <algorithm>
#include <utility>
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <set>
#include <map>
#include <cstring>
#include <time.h>
#define rep(i,n) for(int i=0;i<n;i++)
const int inf=~0U>>1,maxn=10;
using namespace std;
double L[maxn+1][maxn];
double A[maxn][maxn+1];
int n;
inline double sqr(double x)
{
return x*x;
}
void Init()
{
cin>>n;
rep(i,n+1)
rep(j,n)cin>>L[i][j];
rep(i,n)
{
double*Line=A[i];
double*a=L[i],*b=L[i+1];
Line[n]=0;
rep(j,n)Line[n]+=sqr(a[j])-sqr(b[j]),Line[j]=2*(a[j]-b[j]);
}
}
void Solve()
{
rep(i,n)
{
double t=A[i][i];
rep(j,n+1)A[i][j]/=t;
rep(j,n)if(j!=i)
{
double r=A[j][i];
rep(k,n+1)A[j][k]-=r*A[i][k];
}
}
rep(i,n)printf("%0.3lf ",A[i][n]);
}
int main()
{
//freopen("in","r",stdin);
Init();
Solve();
}

本高亮代码使用codeHl生成,

[POI2009]Baj 最短回文路

[POI2009]Baj 最短回文路

Time Limit:10000MS  Memory Limit:165536K
Total Submit:10 Accepted:1
Case Time Limit:3000MS

Description

N个点用M条有向边连接,每条边标有一个小写字母。

对于一个长度为D的顶点序列,回答每对相邻顶点Si到Si+1的最短回文路径。

如果没有,输出-1。

如果有,输出最短长度以及这个字符串。

Input

第一行正整数N和M ( 2 ≤ N ≤ 400 , 1 ≤ M ≤ 60,000 )
接下来M行描述边的起点,终点,字母。
接下来D表示询问序列长度 ( 2 ≤ D ≤ 100 )
再接下来D个1到N的整数

Output

对于D-1对相邻点,按要求输出一行。
如果没合法方案,输出-1。

如果有合法,输出最短长度以及这个字符串。空格隔开。

Sample Input

6 7

1 2 a

1 3 x

1 4 b

2 6 l

3 5 y

4 5 z

6 5 a

3

1 5 3

Sample Output

3 ala

-1

Source
首先一开始我的想法是对于
(a,b)如果a->c的边和b->c上的边的字母一样的话就可以转移。。然后状态就是(a,b)。。
这样状态数有N^2。。每次转移是度数的平方级别的。。显然会TLE囧。。。
然后换种思路:
这个更新说白了就是a走一步,b顺着同样的边走一步。
那么有两种可能的情况轮到a走,轮到b走。。
如果是a走,那么a随便走一步就行了。。
如果是b走,b要跟a走到那个一样。。
换言之状态就是 (a,b,now,pre)a和b意义如上,now表示是a走还是b走,pre表示上一个是哪个(a走到话就忽略)。。
那么实际上就一共有N*N*(26+1)种状态。。同时更新也变成O(M)级别了。。
A了。。代码如下。。。
http://www.ideone.com/EpXy9

Page 2 of 41234