Bonus 奖励计划

Bonus 奖励计划

Time Limit:3000MS Memory Limit:65536K
Total Submit:58 Accepted:16
Case Time Limit:1000MS

Description


Input

请做到文件底结束,对于每一组:
第一行包含一个正整数N,表示城市的数目。
接下来的N-1行,每行包含2个整数,Ai、Bi,表示Ai和Bi间有一条双向的旅行通道。

Output

对于每一组测试数据,输出一行:
为一个实数,表示平均的支付费用,保留(四舍五入)至小数点后6位。

Sample Input

Sample Output

Hint

10%的数据中N ≤ 10;
30%的数据中N ≤ 100;
50%的数据中N ≤ 1000。
100%的数据中2 ≤ N ≤ 10000,T ≤ 10,1 ≤ Ai,Bi ≤ N,Ai≠Bi。
数据保证任意两个城市之间有且只有一条路径(Path)。

Source

北京2010
额。。看上去很难实际上还是挺水滴。。关键是给每条边的边权赋值成这个点被穿过的概率。。那么答案就是所有路径长度的平均值。。
Code:
#include <vector>
#include <algorithm>
#include <utility>
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#define tr(e,x) for(it e=x.begin();e!=x.end();e++)
#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++)
const int inf=~0U>>1,maxn=10000;
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int>::iterator it;
vector<int> E[maxn];
int n,Size[maxn];
double Ans,Sum[maxn];
void Clear()
{
    rep(i,maxn)E[i].clear();
}

void AddEdge(int s,int t)
{
    E[s].pb(t);E[t].pb(s);
}

bool Init()
{
    Clear();
    if(scanf("%d",&n)!=1)return false;

    int s,t;
    rep(i,n-1)
    {
        scanf("%d%d",&s,&t);
        –s;–t;
        AddEdge(s,t);
    }

    return true;
}
void Dfs(int x,int f)
{
    Size[x]=1;Sum[x]=0;
    tr(e,E[x])if(*e!=f)
    {
        Dfs(*e,x);
        Size[x]+=Size[*e];
    }
    tr(e,E[x])if(*e!=f)
    {
        double c=double(Size[*e])*(n-Size[*e])/(n*(n-1)/2);
        //cout<<(*e)<<"<->"<<x<<":"<<c<<endl;
        Sum[x]+=Size[*e]*c+Sum[*e];
        Ans+=(Size[x]-Size[*e])*(Sum[*e]+c*Size[*e]);
    }
}

void Solve()
{
    Ans=0;
    Dfs(0,-1);
    printf("%0.6lfn",Ans/((n-1)*n/2));
}
int main()
{
    //freopen("in","r",stdin);
    while(Init())Solve();
}

1.0000000.8888890.7500000.84000021 231 22 341 21 31 451 25 22 34 3

棋盘游戏

棋盘游戏

Time Limit:5000MS Memory Limit:65536K
Total Submit:21 Accepted:8
Case Time Limit:500MS

Description

有一个100 * 100的棋盘,其中左下角的编号为(0, 0), 右上角编号为(99, 99)。棋盘上有N个Queen,最开始第i个Queen的位置为(Xi, Yi)。现在有两个玩家依次来操作,每一次一个玩家可以选择其中一个Queen,将它跳到(Xi – k, Yi)或(Xi, Yi – k)或(Xi – k, Yi – k), 其中k > 0。注意在游戏的过程中,一个格子里面可能出现多个Queen。如果谁先将任意一个Queen移动到(0, 0), 谁就获胜。问先手必胜还是后手必胜?

Input

注意本题是多组数据。
第一行有一个数T, 表示数据组数。
接下来有T组数据,每组数据的第一行一个正整数N表示Queen的个数。接下来N行每行两个数表示第i个Queen的初始位置Xi, Yi(0 <= Xi <= 99, 0 <= Yi <= 99)。

Output

对于每一组数据,你需要输出是先手必胜还是后手必胜。
如果是先手必胜,输出“^o^“, 如果是后手必胜,输出”T_T”。

Sample Input

Sample Output

Source
囧。马上要期末考了。。颓废了半天。做道题放松一下。。
。这题让我更加深入的领会了Game Theory
首先看看有没有棋子可以一步到达(0,0)的。。有的话就先行者胜。。
然后把所有(0,x),(x,0),(x,x)都看成必败态。。让其SG值为0.。接着算出所有其它点的SG值
Xor一下就OK了。。
上次忘发代码了悲剧囧。。补一下。。
Code:
#include <vector>

#include <algorithm>
#include <utility>
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cstring>
#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++)
const int inf=~0U>>1,maxn=100;
using namespace std;
int Dp[maxn][maxn];
bool Set[maxn*3];
void Insert(int a,int b)
{
    if(a>0&&b>0&&a!=b)Set[Dp[a][b]]=true;
}
void PreDo()
{
    for(int i=1;i<maxn;i++)
        for(int j=1;j<maxn;j++)
        {
            memset(Set,0,sizeof Set);
            if(i!=j)
            {
                for(int k=1;k<maxn;k++)
                {
                    Insert(i-k,j);
                    Insert(i,j-k);
                    Insert(i-k,j-k);
                }
            }
            int&t=Dp[i][j]=0;
            while(Set[t])t++;
        }
}
void Solve()
{
    int n,x,y,s=0;bool win=false;
    scanf("%d",&n);
    rep(i,n)
    {
        scanf("%d%d",&x,&y);
        if(x==0||y==0||x==y)win=true;
        else s^=Dp[x][y];
    }
    if(win||s)puts("^o^");
    else puts("T_T");
}
int main()
{
    //freopen("in","r",stdin);
    PreDo();
    int t;cin>>t;rep(i,t)Solve();
}

^o^T_T数据范围T <= 10, N <= 1000

223 43 533 24 23 1

[BeiJing2010]取数游戏 game

[BeiJing2010]取数游戏 game

Time Limit:10000MS Memory Limit:65536K
Total Submit:16 Accepted:9
Case Time Limit:1000MS

Description

小 C 刚学了辗转相除法,正不亦乐乎,这小 P 又出来捣乱,给小 C 留了个
难题。
给 N 个数,用 a1,a2…an来表示。现在小 P 让小 C 依次取数,第一个数可以
随意取。假使目前取得 aj,下一个数取ak(k>j),则ak必须满足gcd(aj,ak)≥L。
到底要取多少个数呢?自然是越多越好!
不用多说,这不仅是给小 C 的难题,也是给你的难题。

Input

第一行包含两个数N 和 L。
接下来一行,有 N 个数用空格隔开,依次是 a1,a2…an。

Output

仅包含一行一个数,表示按上述取法,最多可以取的数的个数。

Sample Input

Sample Output

Hint

选取 3个数16、24、6。gcd(16,24)=8,gcd(24,6)=6。

2≤L≤ai≤1 000 000;
30% 的数据N≤1000;
100% 的数据 N≤50 000

Source
额。。这题感觉跟VIJOS上一题一样。。记Dpi表示以i的倍数为结尾的最长长度。。然后Dp一下就可以了。。

#include <algorithm>#include <cstdio>#define rep(i,n) for(int i=0;i<n;i++)const int inf=~0U>>1,maxw=1000000,maxp=10000;using namespace std;int Dp[maxw+1]={},n,L,List[maxp];int main(){ scanf("%d%d",&n,&L); rep(i,n) { int x,tmp=0,c=0; scanf("%d",&x); for(int i=1;i*i<=x;i++) if(x%i==0) { if(i>=L)List=i; if(x/i>=L)List=x/i; } rep(i,c)tmp=max(tmp,Dp[List[i]]);tmp++; rep(i,c)Dp[List[i]]=tmp; } int ans=0; rep(i,maxw+1)ans=max(ans,Dp[i]); printf("%dn",ans);}35 6 7 16 9 24 6

[POI2007]Zap

[POI2007]Zap

Time Limit:10000MS Memory Limit:165536K
Total Submit:176 Accepted:34
Case Time Limit:2000MS

Description

FGD正在破解一段密码,他需要回答很多类似的问题:对于给定的整数a,b和d,有多少正整数对x,y,满足x<=a,y<=b,并且 gcd(x,y)=d。
作为FGD的同学,FGD希望得到你的帮助。

Input

第一行包含一个正整数n,表示一共有n组询问。(1<=n<= 50000)
接下来n行,每行表示一个询问,每行三个正整数,分别为a,b,d。(1<=d<=a,b<=50000)

Output

对于每组询问,输出到输出文件zap.out一个正整数,表示满足条件的整数对数。

Sample Input

Sample Output

Hint

对于第一组询问,满足条件的整数对有(2,2),(2,4),(4,2)。
对于第二组询问,满足条件的整数对有(6,3),(3,3)。

Source
额。。这题十分的那个啥。。。。Orz oimaster神牛!!!
首先对付这种复杂的问题只有容斥原理了。。
只需要算出G(x,y):1<=i<=a,1<=j<=b且(i,j)=1的就可以了。。
F(a,b,k)表示1<=i<=a,1<=j<=b且(i,j)>=k的对数,很显然为a/k*b/k。。
那么G(a,b)=1*F(a,b,1)-F(a,b,2)….注意对每个k来说,无论a和b,系数是固定的。。
同时a/k*b/k按相同值分段可以分成Sqrt级别。。所以预处理一下系数的部分和就OK了。。
代码长度最短囧。。。

#include <algorithm>#include <cstdio>#define rep(i,n) for(int i=0;i<n;i++)const int maxn=50000+10;using namespace std;int P[maxn]={};int get(int i){ int s=1; for(int x=2;x*x<=i;x++)if(i%x==0) { i/=x;if(i%x==0)return 0; s*=-1; } if(i>1)s*=-1; return s;}int main(){ for(int i=1;i<=maxn;i++)P[i]=P[i-1]+get(i); int a,b,k,n;scanf("%d",&n); rep(i,n) { scanf("%d%d%d",&a,&b,&k);a/=k;b/=k; if(a>b)swap(a,b); int ans=0; for(int t=1;t<=a;t++) { int m=min(a/(a/t),b/(b/t))-t; ans+=(P[t+m]-P[t-1])*(a/t)*(b/t); t+=m; } printf("%dn",ans); }}3224 5 26 4 3

[POI2006]Szk-Schools

[POI2006]Szk-Schools

Time Limit:5000MS Memory Limit:65536K
Total Submit:34 Accepted:21
Case Time Limit:1000MS

Description

Input

Output

如果有可行解, 输出最小代价,否则输出NIE.

Sample Input

Sample Output

Source
费用流TLE。。只好学了个KM算法来对付这题囧。。

#include <vector>#include <algorithm>#include <utility>#include <iostream>#include <cstdio>#include <cmath>#include <cstdlib>#include <cstring>#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++)const int inf=~0U>>2,maxn=200;using namespace std;typedef long long ll;typedef unsigned long long ull;int Lx[maxn],Ly[maxn],w[maxn][maxn],Link[maxn],Slack[maxn],n;bool VisX[maxn],VisY[maxn];bool Find(int x){ VisX[x]=true; rep(y,n)if(!VisY[y]) { int t=Lx[x]+Ly[y]-w[x][y]; if(!t) { VisY[y]=true; if(Link[y]==-1||Find(Link[y])) return Link[y]=x,true; } else Slack[y]=min(Slack[y],t); } return false;}void KM(){ memset(Link,-1,sizeof Link); rep(i,n)Lx[i]=-inf; memset(Ly,0,sizeof Ly); rep(i,n)rep(j,n)Lx[i]=max(Lx[i],w[i][j]); rep(x,n) { rep(y,n)Slack[y]=inf; for(;;) { memset(VisX,0,sizeof VisX); memset(VisY,0,sizeof VisY); if(Find(x))break; int d=inf; rep(y,n)if(!VisY[y])d=min(d,Slack[y]); rep(x,n)if(VisX[x])Lx[x]-=d; rep(y,n)if(VisY[y])Ly[y]+=d;else Slack[y]-=d; } }}void InIt(){ cin>>n;int m,a,b,k; rep(x,n)rep(y,n)w[x][y]=-inf; rep(x,n) { scanf("%d%d%d%d",&m,&a,&b,&k);–a;–b;–m; for(int y=a;y<=b;y++) w[x][y]=-abs(y-m)*k; }}int main(){ //freopen("in","r",stdin); InIt();KM();int ans=0; rep(i,n) { int tmp; if((tmp=w[Link[i]][i])==-inf){cout<<"NIE"<<endl;return 0;} ans-=tmp; } cout<<ans<<endl;}951 1 2 31 1 5 13 2 5 54 1 5 103 3 3 1

网易有道在线赛

好吧这个比赛的题目太BT了。。完全没有思路。。。
A想了半天想出了个贪心。。就是从A开始像PRIM最小生成树一样计算最小生成树,
每次扩展离ch最远的节点。。只有21分。。(后来我交这个有81分。。我怀疑数据在变。。)
然后我只好想办法骗点分。。我想了半天只能搜索。。每次搜索扩展那个节点,然后判断一下ch是不是能到达所有的没有扩展到节点。。。我感觉效率非常烂。。肯定要挂。然后我想到原来那个贪心。。决定按离ch的距离从小到大搜。。结果24分。。然后我改掉了几个错误,45分了。。看了一会儿。。又改掉了几个错误。。81分了。。。
此时突然发现有个回溯后的恢复没有加上,加上后TLE到3分。。
震惊了。。
然后我灵感爆发,决定随机化恢复不恢复回溯,一开始是1/2不恢复,87,
1/8 93
1/256 96
1/2048 99
就这么AC了。。。
B题目都没看。。
C一开始就觉得要考虑各种各样的情况,非常的复杂,用Java写了半天都要吐了。。。最后看到A改成部分分了。。果断放弃去骗A的分。。
教主真是太神了!!!Orz到极点啊!!!!!
BS有道啊,什么有道难题啊,全是难题啊。。。
发现C居然是CTSC的题目。。。无语到极点。。。

Page 1 of 3123