USACO OPEN 2010

真是悲剧阿。。第一题我想到了dP但因为我以为回来前只能跳一次导致噢只对了3个。。第二题我DP写对了。。但是没用long long。。WA一个点。。第3题悲剧了。。骗分都没写。。OrzWinmad神牛AC!!

370

题目在http://acm.sgu.ru/problem.php?contest=0&problem=370
首先特判掉n=1或m=1或n、m都等于1的情况。。
然后答案就是p<=n&&p<=m&&(p,q)=1的数对的个数。。
很明显可以用容斥原理做。。
就OK了。。

#include<iostream>#include<vector>#include<algorithm>#include<cstring>using namespace std;const int maxn=1000000+1;int n,m,pnt,*P;long long ans=0;int S[maxn][10],D[maxn]={};void dfs(int p,int ch,int now){ if(now>n)return; if(p==pnt) { if(ch&1)ans-=n/now; else ans+=n/now; return; } dfs(p+1,ch,now); dfs(p+1,ch+1,now*P[p]);}int main(){ //freopen("in","r",stdin); cin>>n>>m;n–;m–; if(m>n)swap(n,m); if(!n){cout<<0<<endl;return 0;} if(!m){cout<<1<<endl;return 0;} for(int i=1;i<=m;i++) { if(i==1){ans+=n;continue;} int t=i,a;P=S[i]; for(a=2;a*a<=t;a++) if(t%a==0) { while(t%a==0){t/=a;} break; } if(t==i)P[D[i]++]=t; else { D[i]=D[t]+1; memcpy(P,S[t],sizeof(S[t])); P[D[i]-1]=a; } pnt=D[i]; dfs(0,0,1); } cout<<ans+2<<endl;}

COCI 2010-7题解

哎。。我真是太菜了。。
30,50:忽略啦。。
70:这道题直接按距离从小到大处理每一对L和X的关系,关键是因为题目中有一个信息所没有两个L跟一个X一样近,所以实际上X和L的数量不会非常多的,这样子是不会TLE的囧。。我在写的时候是照曼哈顿距离写的。。居然会有49分。。天哪囧。。。
100:根据最小生成树的计算可以把一个环上的最大边忽略掉,可以发现除了分别按X,Y,Z排序的相邻点之间的边之外的边,都可以忽略掉囧。。所以之后之间用Kruskal就OK了。。
120:注意到两点之间的距离就是X,Y轴差的最大值。。注意到|A+B|+|A-B|=Max(A,B)*2,所以将每个点的坐标由(x,y)->(x+y,x-y)。。那么题目中定义的距离就变成曼哈顿距离了。。曼哈顿距离就好算了(*^__^*) 嘻嘻……。。。这样的变换好像在IOI中出现过。。哎。。。悲剧。。
130:晕。。这不就是SGU的原题么。。当时我SB了囧。。首先由1度点之间判不行。。否则不断找欧拉回路。。对这个回路用间隔染色来染色。。特判一下整个图为奇环的情况就OK了。。

COCI 2010-7

这次的题目好难好BT啊囧。。。
30:这题是水题。。
50:个人感觉是二进制位数-最后一位位置+1不知道为什么错了一个点
70:模拟题,我好像模拟烂了。。只有49分囧。。
100:给空间中n个点,定义距离为三个纬度中最短的差,求最小生成树,想了半天想了个很复杂的算法,算法度很难估计,只好上暴力,居然有50分晕。。
120:这题我看到题目中说有60%的数据n,m<=300,于是对于每个点先枚举斜着走的方向,再分别统计,是n*m*(n+m)的。。得了60分。。
150:去死吧。。根本不会。一开始我想是不是用随机化骗点分。。但是太困了编不下去了囧。。。
最后得了234分。。太菜了。。悲剧。。
哎。。买了台HD2。。真是帅呆了。。实际上WM也不错啊。。
不过还是暑假的时候去把这个刷成Android吧。。
PS。。最近好像什么OJ都挂了。。VIJOS,八中OJ,连PKU都不能上了囧。。

BeJing ICPC 2007 Jewel Trading

acmicpc-live-archive.uva.es/nuevoportal/
题目在UVA上。。。
这道题首先可以列个Dp方程出来
设F[n]为还有n次就要以a价格卖出的最大期望收入,那么
F[n]=Max{ (p-F[n-1])/(1+(p-a)^b) }+F[n-1]…p为大于a的整数。。
由于决策有无限个。。一般的Dp都悲剧了。。
一开始我用微积分算出这个式子关于p的导数,然后想直接用数学方法求出最大值,失败了。。
不过我根据数学观察发现这个导数是单调递减的,也就是说这个函数是单峰的,
于是就可以二分搜索出最大值囧。。。
额。。看来前段时间苦学数学也是有好处的囧。。。
Code:
#include <algorithm>
#include <cstdio>
#include <iostream>
#include <cmath>
#define rep(i,n) for(int i=0;i<n;i++)
#define pb push_back
using namespace std;
const int maxn=100+1,inf=~0U>>2;
int n,a;double b,F[maxn];
int main()
{
//freopen("in","r",stdin);
for(int num=1;;num++)
{
cin>>n>>a>>b;if(!n)break;
F[0]=a;n–;
for(int i=1;i<=n;i++)
{
int l=a+1,r=inf;
#define get(p) (p-F[i-1])/(1+pow(p-a,b))
while(l+1<r)
{
int m=(l+r)/2;
if(get(m+1)-get(m)>=0)
l=m;
else
r=m;
}
F[i]=max(get(l),get(r))+F[i-1];
}
printf("Case %d: %0.2lfn",num,F[n]);
}
}

BeJing ICPC 2007 Color Squares

题目在UVA上。http://acm.uva.es/archive/nuevoportal/
一开始我的想法是搜索。。然后写了N个剪枝。。搞的累死。。结果却发现根本不行。。
我测了一下发现一组数据差不多0.2s。。但这玩意数据多的吓人。。TLE。。。
后来我感觉应该从这么多数据中找共同点。就是预处理一下。。
由于棋盘是一样的,所以能放的状态是有限的,
所有状态可以用它能分别放B-Y的个数和其需要的布数来表示,
只有步数最小的才予以考虑,那么只要开个4维数组记录所有状态就可以了。。、
由于没有剪枝,暴力搜出所有状态需要4s+。。但之后只要枚举4种颜色的个数就OK了。。
所以程序飞快,AC了(*^__^*) 嘻嘻
Code:
#include <vector>#include <algorithm>#include <utility>#include <iostream>#include <cstdio>#include <cmath>#include <cstdlib>#define rep(i,n) for(int i=0;i<n;i++)#define pb push_backconst int inf=~0U>>1;using namespace std;int D[10][10][10][10]={0};int w[4],W,cnt=0;int a[4]={0};int M[3][3]={0};bool check[4];const int di[]={0,1,0,-1},dj[]={1,0,-1,0};inline bool Legal(int i,int j){ return i>=0&&i<3&&j>=0&&j<3;}void Fill(int p,int i,int j,int s){ //cout<<p<<" "<<i<<" "<<j<<" "<<s<<endl; if(p==4) { int&x=D[a[0]][a[1]][a[2]][a[3]]; if(!x||x>s)x=s;cnt++; return; } if(i==3) { Fill(p+1,0,0,s); return; } int ii,jj; memset(check,0,sizeof(check)); rep(d,4) { ii=di[d]+i;jj=dj[d]+j; if(Legal(ii,jj)&&M[ii][jj]) check[M[ii][jj]-1]=true; } if(j==2)ii=i+1,jj=0; else ii=i,jj=j+1;bool c=true; rep(x,p)if(!check[x])c=false; Fill(p,ii,jj,s);if(!c)return; int om=M[i][j]; M[i][j]=p+1; a[p]++;if(om)a[om-1]–; Fill(p,ii,jj,s+1); a[p]–;if(om)a[om-1]++; M[i][j]=om;}int main(){ //freopen("in","r",stdin); Fill(0,0,0,0); for(int num=1;;num++) { rep(i,4)cin>>w[i];if(!w[0])break; cin>>W; int ans=100,s=0; for(int a=0;a<=9;a++) { s+=a*w[0]; for(int b=0;a+b<=9;b++) { s+=b*w[1]; for(int c=0;a+b+c<=9;c++) { s+=c*w[2]; for(int d=0;a+b+c+d<=9;d++) { s+=d*w[3];int x=D[a][b][d]; //cout<<a<<" "<<b<<" "<<c<<" "<<d<<" "<<s<<" "<<x<<endl; if(x&&s>=W)ans<?=x; s-=d*w[3]; } s-=c*w[2]; } s-=b*w[1]; } s-=a*w[0]; } cout<<"Case "<<num<<": "; if(ans==100)cout<<"Impossible"<<endl; else cout<<ans<<endl; }}

ICPC World Finals-2010

看了看WF 2010的题目。。发现好难啊天哪。。我真是太弱菜啦悲剧。。。
Problem A:
烦的跟鬼一样的模拟题,而且情况很多。。我好不容易搞懂了题目已经半疯了。。

Problem C:
离散化一下。。然后倒过来求出能到达终点的面积就OK了。。

Problem E:
这到题是裸的带连通性的状态压缩问题啊,直接上状态压缩Dp。。为了重建路径干脆把路径保存在状态里面好了。反正空间够的。。

Problem G:
还算简单的动归题。。。

Problem I:
有点意思饿。。就是一个n*m的图,给你三个点以及它们必须在那个次序到达,让你统计满足这个条件的从左上角到左下角的路径数。。说白了还是带连通性的状态压缩问题。。关键是要记录一些附加的量,然后转移的时候小心一点就可以了。。。

Problem J:
这道题说的是给你一个X*Y的矩阵,然后让你用切割的办法(每次必须一刀或横或竖切成两块)分成N块,面积分别为你的N个朋友的要求面积。。
1<=X,Y<=100,N<=15。。很显然要Dp。。状态就是当前矩形的长宽,还有当前矩形要切出的子集。。但是这样的话状态会很多。。实际上不多,因为当前矩形的面积一定等于当前子集的和。所以开个Map保存所有状态就OK了。。

[Usaco2008Nov]安慰奶牛cheer

[Usaco2008Nov]安慰奶牛cheer

Time Limit:10000MS Memory Limit:165536K
Total Submit:18 Accepted:15
Case Time Limit:1000MS

Description

Farmer John变得非常懒, 他不想再继续维护供奶牛之间供通行的道路. 道路被用来连接N
(5 <= N <= 10,000)个牧场, 牧场被连续地编号为1..N. 每一个牧场都是一个奶牛的家.
FJ计划除去P(N-1 <= P <= 100,000)条道路中尽可能多的道路, 但是还要保持牧场之间
的连通性. 你首先要决定那些道路是需要保留的N-1条道路.

第j条双向道路连接了牧场S_j和E_j (1 <= S_j <= N; 1 <= E_j <= N; S_j != E_j),
而且走完它需要L_j (0 <= L_j <= 1,000)的时间. 没有两个牧场是被一条以上的道路所连接.

奶牛们非常伤心, 因为她们的交通系统被削减了. 你需要到每一个奶牛的住处去安慰她们. 每次
你到达第i个牧场的时候(即使你已经到过), 你必须花去C_i (1 <= C_i <= 1,000)的
时间和奶牛交谈.

你每个晚上都会在同一个牧场(这是供你选择的)过夜, 直到奶牛们都从悲伤中缓过神来. 在早上
起来和晚上回去睡觉的时候, 你都需要和在你睡觉的牧场的奶牛交谈一次. 这样你才能完成你的
交谈任务.

假设Farmer John采纳了你的建议, 请计算出使所有奶牛都被安慰的最少时间.

对于你前10次的提交, 你的程序会在一部分正式的测试数据上运行, 并且返回运行的结果.

程序名: cheer

Input

* 第 1 行: 用空格隔开的两个整数N和P
* 第 2..N+1 行: 第i+1行包含了一个整数: C_i
* 第 N+2..N+P+1 行: 第 N+j+1 行包含用空格隔开的三个整数: S_j, E_j 和 L_j

Output

第 1 行: 一个整数, 所需要的总时间(包含和在你所在的牧场的奶牛的两次谈话时间).

Sample Input

Sample Output

Source
饿..这道题还是有点意思的…首先要我们求一个生成树..那么尝试着转化成最小生成树问题,对于每条边,如果选的话,则要耗去来回一趟和访问2个端点的时间,重加一下权就可以了,最后选择最小的哪个节点当出发点就行了。..
Code:

#include<iostream>#include<cstdio>#include<algorithm>#include<queue>#define rep(i,n) for(int i=0;i<n;i++)using namespace std;const int maxn=10000;int n,m;struct uf{ int F[maxn]; uf(){rep(i,n)F[i]=i;} int Find(int i) { return i==F[i]?i:(F[i]=Find(F[i])); } bool Find(int i,int j) { i=Find(i);j=Find(j); return F[i]=j,i!=j; }};struct Edge{ int s,t,c; Edge(int _s,int _t,int _c):s(_s),t(_t),c(_c){} bool operator<(const Edge&o)const { return c>o.c; }};priority_queue<Edge> PQ;int C[maxn];int main(){ //freopen("in","r",stdin); cin>>n>>m;int s,t,c,ans=~0U>>1; rep(i,n)scanf("%d",C+i),ans<?=C[i]; rep(i,m)scanf("%d%d%D",&s,&t,&c),–s,–t,PQ.push(Edge(s,t,c*2+C[s]+C[t])); uf U; while(n>1) { Edge e=PQ.top();PQ.pop(); if(U.Find(e.s,e.t)) ans+=e.c,n–; } cout<<ans<<endl;}176输出解释:保持这些路径: 1-(5)-2-(5)-3 5 / (12) /(12) *4——+从牧场4起床, 然后按照 4, 5, 4, 2, 3, 2, 1, 2, 4 的顺序来访问奶牛们, 总共需要176个单位的时间.5 71010206301 2 52 3 52 4 123 4 172 5 153 5 64 5 12输入解释: +-(15)-+ / / 1-(5)-2-(5)-3-(6)–5 /(17) / (12) / /(12) 4——+

[HNOI2003]激光炸弹

[HNOI2003]激光炸弹

Time Limit:10000MS  Memory Limit:165536K
Total Submit:49 Accepted:20
Case Time Limit:1000MS

Description

一种新型的激光炸弹,可以摧毁一个边长为R的正方形内的所有的目标。现在地图上有n(N<=10000)个目标,用整数Xi,Yi(其值在 [0,5000])表示目标在地图上的位置,每个目标都有一个价值。激光炸弹的投放是通过卫星定位的,但其有一个缺点,就是其爆破范围,即那个边长为R的 正方形的边必须和x,y轴平行。若目标位于爆破正方形的边上,该目标将不会被摧毁。 0

Input

输入文件的第一行为正整数n和正整数R,接下来的n行每行有3个正整数,分别表示

Output

输出文件仅有一个正整数,表示一颗炸弹最多能炸掉地图上总价值为多少的目标(结果不会超过32767)。

Sample Input

2 1
0 0 1
1 1 1

Sample Output

1
这道题本来应该是用扫描线+线段树做的,但我很无耻的直接暴力枚举正方形。。也是能过的囧
。。。
Code:
#include <vector>
#include <cstdio>
const int maxc=5002;
using namespace std;
int T[maxc][maxc]={0},n,r;
int main()
{
scanf("%d %d",&n,&r);
int x,y,c,a,ans=0;
while(n–)scanf("%d%d%d",&x,&y,&c),T[x+1][y+1]=c;
for(int i=1;i<maxc;i++)
for(int j=1;j<maxc;j++)
T[i][j]+=T[i-1][j]+T[i][j-1]-T[i-1][j-1];
for(int i=0;i+r<maxc;i++)
for(int j=0;j+r<maxc;j++)
if((a=T[i+r][j+r]+T[i][j]-T[i+r][j]-T[i][j+r])>ans)
ans=a;
printf("%dn",ans);
}

Source

数学竞赛。。

额啊。。太悲剧了。。上个星期天我去参加的数学竞赛。。比赛的时候我脑子小了,犯了一堆SB错误。。
球体体积公式记成pi*r^3晕。。
C(a,b)的公式算错了。。
解答题最后一题是一道超级恶心的难题,我做的半死也没做出来,然后对附加题绝望了没去看,结果附加题都很水晕。。。哎。。附加题两题一共50分啊。。
哎。。200分的试卷就考了100分。。我智商真是太低了。。撞死。。
哎。。那天我见到了李恕,莫非我中了吸商光环啊悲剧。。。

Page 1 of 41234