SGU 478. Excursion

acm.sgu.ru/problem.php
我更明白了一个事实,就是我是一个沙茶囧。。
这种题目我在当时比赛的时候居然用带上下界的最大流去做。结果悲剧死。。
实际上简单的贪心就可以了。。如果人变多了让boy回来否则让girl出去。。
Code:
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<utility>
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;
typedef pair<int,int> pi;
const int inf=~0U>>1;
int main()
{
freopen("in","r",stdin);
int b,g,n;
cin>>b>>g>>n;
vector<pi> A;
int now=g;
rep(i,n)
{
int x;cin>>x;
if(x>=now)
{
b-=x-now;
if(b<0) break;
A.push_back(pi(x-now,0));
now=x;
}
else
{
g-=now-x;
if(g<0) break;
A.push_back(pi(0,now-x));
now=x;
}
}
if(A.size()<n)
cout<<"ERROR"<<endl;
else
{
rep(i,n)
cout<<A[i].first<<" "<<A[i].second<<endl;
}
}

【VIJOS 1629】 8

www.vijos.cn/Problem_Show.asp
啥也别说了。。直接上容斥原理。。
Code:
#include<iostream>
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;
const int inf=~0U>>1;
typedef long long ll;
int a,b,A[20],n;
int Count(int a,int b,int x)
{
return b/x-(a-1)/x;
}
ll gcd(ll a,ll b)
{
return b?gcd(b,a%b):a;
}
ll lcm(ll a,ll b)
{
return a/gcd(a,b)*b;
}
ll ans=0;int d;
void dfs(int p,ll s,int ch)
{
if(s>b) return;
if(p==n)
{
int d=Count(a,b,s);
if(ch&1) ans-=d;
else ans+=d;
return;
}
ll NewOne=lcm(s,A[p]);
dfs(p+1,NewOne,ch+1);
dfs(p+1,s,ch);
}
void init()
{
cin>>n;
rep(i,n) cin>>A[i];
cin>>a>>b;
}
int main()
{
//freopen("in","r",stdin);
init();
dfs(0,8,0);
cout<<ans<<endl;
}

[VIJOS 1701] Local Maxima

额。。最为VIJOS回归之后做的第一题。还是蛮有意思的。。
传送门
首先可以看出答案是1到n的倒数和。。
有两个办法。。一个是我开始想到的就是设F(x)为1到x的排列的答案。
那么若这个排列第一个是1。那么就是F(x-1)+1否则在中间的1可以忽略掉,就是F(x-1)。。
那么F(x)=( F(x-1)+1 )/x +F(x-1)*(x-1)/x。。
就是F(x)=F(x-1)+1/x。。。
这个方法只有我这样菜的人才想的出来囧。。
一般来说第i个数为Local Maxima的概率就是他为前i个中最大的概率,就是1/i。。
然后+起来。。
不过数据范围太TMD大了。。
我一开始想是不是要用矩阵加速,感觉不是齐次的搞不出来。。。
最后wiki了一下调和数列,发现原来是有公式的。。
zh.wikipedia.org/wiki/%E6%AC%A7%E6%8B%89-%E9%A9%AC%E6%AD%87%E7%BD%97%E5%B0%BC%E5%B8%B8%E6%95%B0
因为精度的问题,对于n<=10^6次方的时候。。暴力计算,
否则使用公式。
Code:
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<cmath>
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;
const int inf=~0U>>1;
const int limit=1e6;
int main()
{
int n;cin>>n;double ans=0;
if(n<=limit)
for(double i=1;i<=n;i++)
ans+=1/i;
else
ans=log((double)n)+0.57721566490153286060651209;
printf("%0.8lfn",ans);
}P.S我的vijos号由于注册的比较早。不叫WJMZBMR。。好像是453844077囧。。我在想是不是为了统一风格就不要原来的号了又舍不得100多道题目囧。。

Page 7 of 7« First...34567