SRM 476

哎。。真是一场失败的SRM。。Rating没变囧。。
Level I
这么一道水题我只有235分。。实际上只要枚举就行了。但比赛前最后3分钟我发现我的KawiEdit不能用了晕。。结果拼命抢修。。修好后一慌张手速就慢了。。而且我看到这题后立马写二分。。脑缺死了。。n这么小干嘛不枚举啊晕。。
Level II
这个题目太恶心了。。本来我想的完全正确啊。。代码也没有错(一开始我一直以为我概率搞错。。最后发现是题目恶心)。。注意到每个人的friend字符串在36个字符以下。。那么算一下可以发现一个人最多有15个朋友。。关键是题目中有一句话说主人公只会访问自己的朋友。。所以顶点数最多16!!!靠。。
那么就简单了设Dp(Vised,int last)表示访问过了Vised的人,最后一个是last。。首先枚举下一个是哪个。。然后按概率排序。。显然第i个被主人公选择的情况只可能是前i-1个都不幸悲剧了。。第i个又OK。。那么算出这个概率然后+起来就OK了。。
Level III
额。。这题实际上不是非常难啊晕。。我当时完全没有时间去做了悲剧。。
首先注意到这个图是个仙人掌,所以一条边要么是桥要么在一个环里面额。。是桥的话显然要是crewSize。。否则的话考虑这个环,加入这个环离出口最近的是0,其它一次标号为1..n,那么首先如果没有Cabin的话,设L[x]是x到x-1,R[x]是x到x+1的Cabin数量,显然L[x]+R[x]>=crewSize。并且如果L[x]>L[x-1]完全没意义。。所以L[x]<=L[x-1]同理R[x]<=R[x+1]..然后现在有一些Cabin。。那么就跟一个经典问题就是把一个数列通过最小的变换变成单调类似了。。注意到降低显然不需要费用。。那么就OK了。。

原创题[X哥的泡妞计划]

应某人要求将名字改成X哥。。扯蛋的时候现编的题目。。感觉很有意思啊。。
2.X哥的泡妞计划
(paoniu.in/paoniu.out)
英俊潇洒玉树临风的X哥要开始泡妞啦!X哥看上了N个妞比如XX,XXX,XXXX,泡妞,当然是要花钱滴!第i个妞要花掉X哥Vi的钱,可有些女生之间风格差别太大比如XX和XXXX,X哥无法适应囧,因此就不能一起泡啦,有M对这样的女生,第i对是ai和bi。。X哥的母亲知道了这个消息,觉得自己儿媳妇自然是越多越好。。于是给了X哥V的钱,让X哥去泡妞!X哥最多能泡几个妞呢?
数据范围
N<=100 X哥看上的女生不会太多。。
M<= 200
V<= 1000
输入:
第一行是N和M和V
第二行有N个数,分别是Vi
之后每行一对ai和bi

SGU 261. Discrete Roots

给一个素数p,整数k和a
就x^k=a(mod p)的所有整数解。。。
首先算出原根g
设x=g^i(mod p)
则首先若a==0(我就是忘处理这个所以WAN次囧。。)。。那么答案就是0.。
否则a=g^j(mod p)
那么g^(ik)=g^j
<=> ik=j(mod p-1)..
算出所有满足这个的i,代入得到所有x,排序就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++)
#define pb push_back
#define Debug(x) cout<<#x<<"="<<x<<endl;
#define tr(e,x) for(typeof(x.begin()) e=x.begin();e!=x.end();e++)
const int inf=~0U>>1,maxn=20;
using namespace std;
typedef long long ll;
ll P[maxn],m=0,p,g,k,a;
void decompose(ll x)
{
for(ll i=2;i*i<=x;i++)
if(x%i==0)
{
P[m++]=i;
while(x%i==0)x/=i;
}
if(x>1)P[m++]=x;
}
ll ext_gcd(ll a,ll b,ll&x,ll&y)
{
if(!b){x=1;y=0;return a;}
ll tmp=ext_gcd(b,a%b,y,x);y-=x*(a/b);
return tmp;
}
ll pow(ll x,ll e)
{
if(!e)return 1;
ll tmp=pow(x,e/2);tmp*=tmp;tmp%=p;
if(e&1)tmp*=x,tmp%=p;
return tmp;
}
ll inv(ll x)
{
return pow(x,p-2);
}
bool IsRoot(ll a)
{
rep(i,m)
if(pow(a,(p-1)/P[i])==1)return false;
return true;
}
void FindRoot()
{
decompose(p-1);
for(ll i=2;i<p;i++)if(IsRoot(i)){g=i;break;}
}
ll discrete_Log(ll a)
{
map<ll,ll> Map;ll M=sqrt(p)+1;
ll v=inv(pow(g,M));
ll e=1;Map[1]=0;
for(ll i=1;i<M;i++){e=e*g%p;if(!Map.count(e))Map[e]=i;}
for(ll i=0;i<M;i++)
{
if(Map.count(a))return i*M+Map[a];
a=a*v%p;
}
return -1;
}
vector<ll> Solve(ll a,ll b,ll m)
{
ll x,y,d;
d=ext_gcd(a,m,x,y);
vector<ll> A;
if(b%d)return A;
ll t=b/d;x%=m;if(x<0)x+=m;x=x*t%m;
rep(i,d)
{
A.pb(x);
x+=m/d;x%=m;
}
return A;
}
int main()
{
//freopen("in","r",stdin);
cin>>p>>k>>a;
if(a==0){cout<<1<<endl<<0<<endl;return 0;}
FindRoot();
ll Loga=discrete_Log(a);
vector<ll> Logx=Solve(k,Loga,p-1);
cout<<Logx.size()<<endl;
vector<ll> Ans;
tr(it,Logx)
{
ll tmp=pow(g,*it);
Ans.pb(tmp);
}
sort(Ans.begin(),Ans.end());
tr(it,Ans)cout<<*it<<endl;
}

[CROATIAN2009]OTOCI

[CROATIAN2009]OTOCI

Time Limit:50000MS  Memory Limit:165536K
Total Submit:22 Accepted:20
Case Time Limit:5000MS

Description

给出n个结点以及每个点初始时对应的权值wi。起始时点与点之间没有连边。有3类操作:
1、bridge A B:询问结点A与结点B是否连通。如果是则输出“no”。否则输出“yes”,并且在结点A和结点B之间连一条无向边。
2、penguins A X:将结点A对应的权值wA修改为X。
3、excursion A B:如果结点A和结点B不连通,则输出“impossible”。否则输出结点A到结点B的路径上的点对应的权值的和。
给出q个操作,要求在线处理所有操作。
数据范围:1<=n<=30000, 1<=q<=300000, 0<=wi<=1000。

Input

第一行包含一个整数n(1<=n<=30000),表示节点的数目。
第二行包含n个整数,第i个整数表示第i个节点初始时对应的权值。
第三行包含一个整数q(1<=n<=300000),表示操作的数目。
以下q行,每行包含一个操作,操作的类别见题目描述。
任意时刻每个节点对应的权值都是1到1000的整数。

Output

输出所有bridge操作和excursion操作对应的输出,每个一行。

Sample Input

5
4 2 4 5 6
10
excursion 1 1
excursion 1 2
bridge 1 2
excursion 1 2
bridge 3 4
bridge 3 5
excursion 4 5
bridge 1 3
excursion 2 4
excursion 2 5

Sample Output

4
impossible
yes
6
yes
yes
15
yes
15
16

Source
这题做法很多啊。。有动态树、DFS序之类的。。我的算法是最傻叉的一种。。因为我非常的傻叉。。所以我写了个树链剖分来做这个。由于只要求和所以上树状数组就OK啦。。不过由于有+边的操作。。于是设定一个询问耗时上限,如果超过上限就重新剖分,然后+边就直接暴力+就可以了囧。。
Code:
www.ideone.com/ZAZvq

SPOJ 6779. Can you answer these queries VII

题目就是给你一颗树,每次两个操作,一个是询问A到B的路径上边权的最大连续和,还有一个就是将一条路径所有边权修改成一个数。。。
树链剖分。。像一般线段树那样维护4个值。。。还有打标记。。
我写好之后翻了一下oimaster的park的代码。。对神牛的Orz之情如长江之水绵延不绝啊。。。不过我发现我的写法有点诡异。。我好像是完全忽略轻边直接全部都是线段树的。。所以速度好像慢很多囧。。不过似乎好写一点囧。。还有就是在线段树我直接按深度范围当区间了。。
最近树的题目做的好多啊。。接下来去做OTOCI还有QTREE的其他几道好了囧。。
我发现我GSS系列的题目只差GSS2了。。
Code:
www.ideone.com/qoxC6

月下“毛景树”

月下“毛景树”

Time Limit:20000MS  Memory Limit:65536K
Total Submit:77 Accepted:15
Case Time Limit:2000MS

Description

毛毛虫经过及时的变形,最终逃过的一劫,离开了菜妈的菜园。
毛毛虫经过千山万水,历尽千辛万苦,最后来到了小小的绍兴一中的校园里。爬啊爬~爬啊爬~~毛毛虫爬到了一颗小小的“毛景树”下面,发现树上长着 他最爱吃的毛毛果~~~
“毛景树”上有N个节点和N-1条树枝,但节点上是没有毛毛果的,毛毛果都是长在树枝上的。但是这棵“毛景树”有着神奇的魔力,他能改变树枝上毛 毛果的个数:
 Change k w:将第k条树枝上毛毛果的个数改变为w个。
 Cover u v w:将节点u与节点v之间的树枝上毛毛果的个数都改变为w个。
 Add u v w:将节点u与节点v之间的树枝上毛毛果的个数都增加w个。
由于毛毛虫很贪,于是他会有如下询问:
 Max u v:询问节点u与节点v之间树枝上毛毛果个数最多有多少个。

Input

第一行一个正整数N。
接下来N-1行,每行三个正整数Ui,Vi和Wi,第i+1行描述第i条树枝。表示第i条树枝连接节点Ui和节点Vi,树枝上有Wi个毛毛果。
接下来是操作和询问,以“Stop”结束。

Output

对于毛毛虫的每个询问操作,输出一个答案。

Sample Input

4
1 2 8
1 3 7
3 4 9
Max 2 4
Cover 2 4 5
Add 1 4 10
Change 1 16
Max 2 4
Stop

Sample Output

9
16

【Data Range】
1<=N<=100,000,操作+询问数目不超过100,000。
保证在任意时刻,所有树枝上毛毛果的个数都不会超过10^9个。

Source

绍兴一中
没什么好说的。裸的树链剖分。。为了战胜TLE我搞的累死。。最后发现几处地方写错了。。囧。。。线段树维护的时候维护两个标记Add和Same具体操作看代码吧囧。。
我这个干脆就给每个线段树开了个内存池然后变成纯数组了。。。。非常的猥琐。。
Code:
www.ideone.com/oEXcP

Spoj 3974 3974. Another Tree Problem 八中OJ

Spoj 3974 3974. Another Tree Problem

Time Limit:1000MS  Memory Limit:65536K
Total Submit:13 Accepted:2

Description

As you are bound to know by now, a tree is a connected graph
consisting of N vertices and N−1 edges. Trees also have the property
of there being exactly a single unique path between any pair of
vertices.
You will be given a tree in which every edge is assigned a weight –
a non negative integer. The weight of a path is the product of the
weights of all edges on the path. The weight of the tree is the sum of
the weights of all paths in the tree. Paths going in opposite
directions (A to B and B to A) are considered the same and, when
calculating the weight of a tree, are counted only once.
Write a program that, given a tree, calculates its weight modulo 1000000007.

Input

The first line contains the integer N (2 ≤ N ≤ 100 000), the number of vertices
in the tree. The vertices are numbered 1 to N. Each of the following N−1
contains three integers A, B and W (1 ≤ A, B ≤ N, 0 ≤ W ≤ 1000)
describing one edge. The edge connects vertices A and B, and its weight is W.

Output

Output the weight of the tree, modulo 1000000007.

Sample Input

3
3 2 100
2 1 100

Sample Output

10200

Hint

The weight of the path from 1 to 2 is 100
The weight of the path from 2 to 3 is 100
The weight of the path from 1 to 3 is 100 * 100 = 10000
So the weight of the tree is 10000 + 100 + 100 = 10200

Source
靠。。由于我毫无智商。。。这个题目很显然Dfs一下就可以解决了。。但我以前居然写个树的分治去做。。我真是脑缺啊囧。。。。
是在太鄙视自己了。。
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++)
#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(eit e=x.begin();e!=x.end();e++)
const int inf=~0U>>1,maxn=100000,mod=1000000007;
using namespace std;
typedef long long ll;
int n;
struct Edge
{
int t,c;
Edge(int _t,int _c):t(_t),c(_c){}
};
vector<Edge> E[maxn];
typedef vector<Edge>::iterator eit;
void InsEdge(int s,int t,int c)
{
E[s].pb(Edge(t,c));E[t].pb(Edge(s,c));
}
ll pow(int x,int e)
{
if(!e)return 1;
ll tmp=pow(x,e/2);tmp*=tmp;tmp%=mod;
if(e&1)tmp*=x,tmp%=mod;
return tmp;
}
ll Sum[maxn],P,ans=0;
int Q[maxn],F[maxn],h,t;
void BFS(int vs)
{
h=t=0;
for(Q[t++]=vs,F[vs]=-1;h<t;h++)
{
int x=Q[h];
tr(e,E[x])if(e->t!=F[x])
F[e->t]=x,Q[t++]=e->t;
}
for(int i=h-1;i>=0;i–)
{
int x=Q[i];Sum[x]=1;
ll all,tmp,ret=0;
tr(e,E[x])if(e->t!=F[x])
Sum[x]+=Sum[e->t]*e->c,Sum[x]%=mod;
all=Sum[x]+1;
tr(e,E[x])if(e->t!=F[x])
tmp=Sum[e->t]*e->c,tmp%=mod,ret+=(all-tmp)*tmp,ret%=mod;
ret*=P;ret%=mod;if(ret<0)ret+=mod;ans+=ret;ans%=mod;
}
}
int main()
{
//freopen("in","r",stdin);
cin>>n;int s,t,c;
rep(i,n-1)
{
scanf("%d%d%d",&s,&t,&c);–s;–t;
InsEdge(s,t,c);
}
P=pow(2,mod-2);
BFS(0);
cout<<ans<<endl;
}

[Shoi2007]Vote 善意的投票

[Shoi2007]Vote 善意的投票

Time Limit:1000MS  Memory Limit:65536K
Total Submit:59 Accepted:40

Description

幼儿园里有n个小朋友打算通过投票来决定睡不睡午觉。对他们来说,这个问题并不是很重要,于是他们决定发扬谦让精神。虽然每个人都有自己的主见, 但是为了照顾一下自己朋友的想法,他们也可以投和自己本来意愿相反的票。我们定义一次投票的冲突数为好朋友之间发生冲突的总数加上和所有和自己本来意愿发 生冲突的人数。
我们的问题就是,每位小朋友应该怎样投票,才能使冲突数最小?

Input

第一行只有两个整数n,m,保证有2≤n≤300,1≤m≤n(n-1)/2。其中n代表总人数,m代表好朋友的对数。文件第二行有n个整数,第i个整数 代表第i个小朋友的意愿,当它为1时表示同意睡觉,当它为0时表示反对睡觉。接下来文件还有m行,每行有两个整数i,j。表示i,j是一对好朋友,我们保 证任何两对i,j不会重复。

Output

只需要输出一个整数,即可能的最小冲突数。

Sample Input

3 3
1 0 0
1 2
1 3
3 2

Sample Output

1

Hint

在第一个例子中,所有小朋友都投赞成票就能得到最优解

Source

Day2
额。。这个题目显然可以用网络流解决。。但是经Seventh神牛的提醒。。我使用随机化AC了这个。。。
就是随机一个决策出来。。然后把能最大降低冲突数的那个人决策反过来。。不断搞直到局部最优。。
经过测试随机化10次以上会TLE。。3次就可以AC囧。。
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=300;
using namespace std;
int A[maxn],X[maxn],ans=inf,n,m;
bool E[maxn][maxn]={};
void Random()
{
rep(i,n)X[i]=rand()%2;
while(true)
{
int ch,Min=inf,f=-1;
rep(i,n)
{
ch=0;X[i]^=1;
if(X[i]^A[i])ch++;else ch–;
rep(j,n)if(E[i][j])
{
if(X[i]^X[j])ch++;
else ch–;
}
X[i]^=1;
if(ch<Min){Min=ch;f=i;}
}
if(Min>=0)break;
X[f]^=1;
}
int ret=0;
rep(i,n)
{
if(X[i]^A[i])ret+=2;
rep(j,n)if(E[i][j]&&X[i]^X[j])
ret++;
}
ret/=2;
ans=min(ret,ans);
}
int main()
{
//freopen("in","r",stdin);
cin>>n>>m;rep(i,n)cin>>A[i];
int s,t;
rep(i,m)
{
scanf("%d%d",&s,&t);–s;–t;
E[s][t]=E[t][s]=true;
}
rep(i,3)Random();
cout<<ans<<endl;
}

Page 2 of 41234