COCI 2010-4- 3:iks

就是说有N个数。。然后每次可以把一个数的质因子扔给另一个数。。让最终全体数gcd尽量大。。并求出最小步数。。 很明显分质因子讨论。。每个因子算出平均拥有次数(round down)。。然后对每个不够的全部补上就可以了。。 但我0分。。为什么呢?我很迷惑。。后来发现我少写了一行。。该死的样例!
现在直接A掉了。。。555
#include<iostream>
#include<string>
#include<vector>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<set>
using namespace std;
typedef long long ll;
const int maxn=100;
int n,minstep=0;
set<int> Prime;
int A[maxn];
void getPrime(int x)
{
if(x%2==0)    Prime.insert(2);
while(x%2==0) x/=2;
int p=x;
for(int i=3;i*i<=p&&x!=1;i+=2)
while(x%i==0)
{
Prime.insert(i);
x/=i;
}
if(x!=1) Prime.insert(x);
}
vector<int> Ps;
void init()
{
cin>>n;
for(int i=0;i<n;i++)
cin>>A[i],getPrime(A[i]);
Ps=vector<int>(Prime.begin(),Prime.end());
}
int CalAPrime(int x)
{
static int con[maxn];
memset(con,0,sizeof(con));//这行没写。。全部算错。。0分。。TMD
int sum=0;
memset(con,0,sizeof(0));
for(int i=0;i<n;i++)
{
int t=A[i];
while(t%x==0)
con[i]++,t/=x,sum++;
}
int a=sum/n;
for(int i=0;i<n;i++)
if(con[i]<a)
minstep+=a-con[i];
int res=1;for(int i=0;i<a;i++) res*=x;
return res;
}
int main()
{
//freopen("in","r",stdin);
//freopen("out","w",stdout);
init();ll ans=1;
for(int i=0;i<Ps.size();i++)
ans*=CalAPrime(Ps[i]);
cout<<ans<<" "<<minstep<<endl;
}

TopCoder SRM 461 And COCI 2010-4

God今天两场比赛中间一分钟休息都没有。。做的脑子都昏了。。COCI我很悲剧啊。。简单题A掉了。。难的只拿了50分囧。。TopCoder 我居然拿了房间的第一名。。因为Level3的都被Cha掉了。。我Level3写的脑子都晕了。。最后还是没有搞定。。Cha的时候我想Cha别人时发现能Cha的都被Cha掉了。。Level2的程序我自己看的都晕。。根本Cha不了。。Level1太水了。也没人错囧。。Level3被别人眼疾手快Cha掉了。。见鬼了。。我第二题也被System Test搞悲剧掉了。。200多名。。居然直接变成蓝色了。。怎么搞的?

SGU 149

求出一棵树中离每个点最远的点。。 典型的树形DP。。老题了。。看程序吧。。 Java太难写这种题目了。。只好用c++了。。
#include<cstdio>
#include<vector>
#include<utility>
#include<algorithm>
using namespace std;
typedef pair<int,int> pi;
struct edge
{
int t,c;
edge(int _t,int _c):t(_t),c(_c){}
};
const int maxn=10000;
pi ch[maxn];
int f[maxn];
vector<edge> E[maxn];
typedef vector<edge>::iterator it;
void add_edge(int s,int t,int c)
{
E[s].push_back(edge(t,c));
E[t].push_back(edge(s,c));
}
void Renew(pi&o,int x)
{
if(o.second<x)
{
o.second=x;
if(o.first<o.second)
swap(o.first,o.second);
}
}
void Renew(int&x,int c)
{
x=max(x,c);
}
void dfsch(int x,int fa)
{
ch[x]=pi(0,0);
for(it i=E[x].begin();i!=E[x].end();i++)
if(i->t!=fa)
{
dfsch(i->t,x);
Renew(ch[x],ch[i->t].first+i->c);
}
}
void dfsf(int x,int fa)
{
for(it i=E[x].begin();i!=E[x].end();i++)
if(i->t!=fa)
{
Renew(f[i->t],f[x]+i->c);
if(ch[x].first==ch[i->t].first+i->c)
Renew(f[i->t],ch[x].second+i->c);
else
Renew(f[i->t],ch[x].first+i->c);
dfsf(i->t,x);
}
}
int n;
void init()
{
scanf("%d",&n);
for(int s=1,t,c;s<n;s++)
{
scanf("%d %d",&t,&c);
add_edge(s,t-1,c);
}
}
int main()
{
//freopen("in","r",stdin);
//freopen("out","w",stdout);
init();f[0]=0;
dfsch(0,-1);
dfsf(0,-1);
for(int i=0;i<n;i++)
printf("%dn",max(ch[i].first,f[i]));
}

SGU 175

这个题目实际上只要递归的搞下去就可以了。。
脑子一定要清楚。。否则要悲剧的。。
import java.util.*;
import java.math.*;
public class Solution
{
static Scanner in=new Scanner(System.in);
BigInteger value(int x){return BigInteger.valueOf(x);}
static void print(Object x){System.out.println(x);}
static int Code(int n,int q)
{
if(n==1) return 1;
int k=n/2;
if(q<=k) return Code(k,k-q+1)+n-k;
return Code(n-k,n-k-(q-k)+1);
}
public static void main(String args[])
{
int n=in.nextInt();
int q=in.nextInt();
print(Code(n,q));
}
}

SGU 111

就是给你一个1000位以下的数。。求他的平方根(round down)。。
我由于是java的。。但是java中biginteger没有sqrt的功能。。我只好用二分查找了。。
如果位数是n的话。。二分是n的。。乘法是nlogn的。。所以总共就是n^2logn的。
其实是有10n的好办法的。。
不过我太懒了。。
Code:
import java.util.*;
import java.math.*;
public class Main
{
static Scanner in=new Scanner(System.in);
public static void main(String args[])
{
BigInteger l,r,m,x,tmp;
l=BigInteger.valueOf(0);x=in.nextBigInteger();
r=x.abs().add(BigInteger.ONE);
while(l.add(BigInteger.ONE).compareTo(r)==-1)
{
m=l.add(r).divide(BigInteger.valueOf(2));
if(m.multiply(m).compareTo(x)!=1)
l=m;
else
r=m;
}
System.out.println(l);
}
}

Ural 1009,1012,1013 K-based numbers,Version 1-3

暴冷。。直接DP 一个程序A3题。。
Java的高精度实在太无敌了。。
import java.util.*;
import java.math.*;
public class Main
{
static Scanner in=new Scanner(System.in);
public static void main(String args[])
{
int n,k;
BigInteger notZero,zero;
n=in.nextInt();k=in.nextInt();
zero=BigInteger.valueOf(0);notZero=BigInteger.valueOf(k-1);
for(int i=1;i<n;i++)
{
BigInteger nZero,nNotZero;
nZero=notZero;
nNotZero=zero.add(notZero).multiply(BigInteger.valueOf(k-1));
zero=nZero;
notZero=nNotZero;
}
System.out.println(zero.add(notZero));
}
}

Ural 1005

就是说不到20堆石头。分成2大堆。。让他们绝对值最小。。
直接dfs。。第一次用java写这种题。。感觉还不错。。
实际上java跟C++也差不了多少啊。。
还有就是我用java在pku上虐了七八道高精度的题目。。真是爽!

import java.util.*;
class solve
{
static Scanner in=new Scanner(System.in);
int[] W;
int n,allSum,ans;
void work()
{
init();
dfs(0,0);
System.out.println(ans);
}
void init()
{
n=in.nextInt();
W=new int[n];
allSum=0;
for(int i=0;i<n;i++)
{
W[i]=in.nextInt();
allSum+=W[i];
}
ans=allSum;
}
void checkans(int newAns)
{
newAns=newAns<0?-newAns:newAns;
if(newAns<ans) ans=newAns;
}
void dfs(int pos,int sum)
{
if(pos==n) {checkans(allSum-2*sum);return;}
dfs(pos+1,sum+W[pos]);
dfs(pos+1,sum);
}
}
public class Main
{
public static void main(String[] args)
{
solve now=new solve();
now.work();
}
}

SGU 247

知道我为什么这么快么。。因为我。。使用了ST大法!
Java的计算程序。。java里面有biginteger类。。可以用来高精。。
import java.util.*;
import java.math.BigInteger;
import java.io.*;
public class Solution
{
static Scanner in=new Scanner(System.in);
static String solve(Integer p)
{
BigInteger ans=BigInteger.ONE;
for(Integer i=p+1;i<=2*p;i++)
ans=ans.multiply(BigInteger.valueOf(i));
for(Integer i=2;i<=p;i++)
ans=ans.divide(BigInteger.valueOf(i));
ans=ans.divide(BigInteger.valueOf(p));
ans=ans.add(BigInteger.valueOf(2));
return ans.toString();
}
public static void main(String[] args)
throws IOException
{
PrintWriter out=new PrintWriter("out");
int n=in.nextInt();out.println("{0,");
for(int i=1;i<n;i++) out.println("""+solve(i)+"",");
out.println("0,}");
out.close();
}
}因为以前我写过一个c++的打表机。。所以我就用c++交表了。。

Page 4 of 7« First...23456...Last »