2015 German Collegiate Programming Contest (GCPC 15)
B. Bounty Hunter II
给定一张DAG，求一种方案：用最少的路径将所有点覆盖。写了按长度贪心，按出度的贪心。。。果断挂了。下来搜了下题解，看到了二分图。就懂了。。。把点拆开，每个出点最多允许连一个入点，反之也是这样。那不就是二分图最大匹配吗？然后把用到的边加进去，算一下联通的链就行了，然后再考虑一下，既然是一条条链，把他们原先看作一条链，然后再断开，断开的地方加1，就是答案，断开的位置一共就有 (点数-边数-1) 个，那就解决了。
#include <bits/stdc++.h>
#define pb push_back
typedef long long ll;
const int N = 1100;
const int M = 1000002;
const int inf = 0x3f3f3f3f;
using namespace std;
int n;
vector<int> G[N];
int mch[N],nxt[N],used[N];
bool dfs(int u) {
for(int i=0;i<G[u].size();++i) {
int v = G[u][i];
if(used[v]) continue;
used[v] = 1;
if(mch[v]==-1||dfs(mch[v])) {
mch[v] = u;
nxt[u] = v;
return 1;
}
}
return 0;
}
int hungray() {
for(int i=0;i<=n;++i) mch[i] = nxt[i] = -1;
int ans = 0;
for(int i=1;i<=n;++i) {
memset(used,0,sizeof(used));
if(dfs(i)) ++ans;
}
return ans;
}
int main() {
scanf("%d",&n);
for(int i=1;i<=n;++i) {
int m,x;
scanf("%d",&m);
for(int j=1;j<=m;++j)
scanf("%d",&x),G[i].pb(x+1);
}
int ans = hungray();
cout << n - ans << endl;
return 0;
}
E. Change of Scenery
就是让你判断一下是否有两条长度相同的最短路。一开始的思路是，非严格次短路等于最短路，结果A*炸的很严重，然后看了下数据范围，就写了个暴力的枚举最短路上的边然后求次短路，各种优化还是TLE在test57了。然而这题换个思路不就是最短路计数吗？直接在最短路的时候，维护到这点的最短路的数目就行了。然而注意到这个路径数是非常大的，一开始没有管他，让long long自己溢出，觉得到1的可能性太小了吧。。。结果还真刚好溢出到了1。。。出题人真的是nb。。。于是多取了几个模，就解决了。
#include <bits/stdc++.h>
#define PII pair<int,int>
#define MP make_pair
typedef long long ll;
const int N = 20000;
const int M = 2000600;
const ll inf = 10000000000LL;
const ll P = 1e9 + 7;
const ll P1 = 1e8 + 7;
using namespace std;
struct edge{int e,nxt;ll w;}E[M];
int cc,h[N];
void add(int u,int v,ll z) {
E[cc].e=v;E[cc].w=z;E[cc].nxt=h[u];h[u]=cc;++cc;
}
int n,m,k,p[N],A[M],cnt;
struct node{
int x;ll d;
node(){}node(int a,ll b){x=a;d=b;}
bool operator < (const node a)const {
return a.d < d;
}
};
ll dis[N],num[N],num1[N];
int vis[N];
void dij() {
for(int i=1;i<=n;++i)dis[i]=inf;
priority_queue<node> q;
q.push(node(1,0));
dis[1]=0;num[1]=1;num1[1]=1;
while(!q.empty()) {
node tmp = q.top(); q.pop();
int u=tmp.x;
if(vis[u])continue;
vis[u]=1;
for(int i=h[u];~i;i=E[i].nxt) {
int v=E[i].e;
if(dis[v]>dis[u]+E[i].w) {
dis[v]=dis[u]+E[i].w;
num[v]=num[u];
num1[v]=num1[u];
q.push(node(v,dis[v]));
}
else if(dis[v]==dis[u]+E[i].w) {
num[v]=(num[v]+num[u])%P;
num1[v]=(num1[v]+num1[u])%P1;
}
}
}
return;
}
int main() {
scanf("%d%d%d",&n,&m,&k);
for(int i=1;i<=n;++i) h[i]=-1;
int x;
for(int i=1;i<=k;++i) scanf("%d",&p[i]);
for(int i=1;i<=m;++i) {int x,y;ll z;
scanf("%d%d%I64d",&x,&y,&z);
if(x>y) swap(x,y);
add(x,y,z),add(y,x,z);
}
dij();
if(num[n]!=1)puts("yes");
else if(num1[n]!=1)puts("yes");
else puts("no");
return 0;
}
F. Divisions
直接大数分解，然后约数个数定理
#include <bits/stdc++.h>
typedef long long ll;
#define inf 1000000000
using namespace std;
ll read() {
ll x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
ll gcd(ll a,ll b) {return b==0?a:gcd(b,a%b);}
int n;
ll x,mx;
vector<ll> q;
ll mul(ll a,ll b,ll p) {
ll tmp=(a*b-(ll)((long double)a/p*b+1e-8)*p);
return tmp<0?tmp+p:tmp;
}
ll pow(ll a,ll b,ll p) {
ll ans=1;a%=p;
for(ll i=b;i;i>>=1,a=mul(a,a,p))
if(i&1)ans=mul(ans,a,p);
return ans;
}
bool check(ll a,ll n,ll r,ll s) {
ll ans=pow(a,r,n),p=ans;
for(int i=1;i<=s;i++) {
ans=mul(ans,ans,n);
if(ans==1&&p!=1&&p!=n-1)return 1;
p=ans;
}
if(ans!=1)return 1;
return 0;
}
bool MR(ll n) {
if(n<=1)return 0;
if(n==2)return 1;
if(n%2==0)return 0;
ll r=n-1,s=0;
while(r%2==0)r/=2,s++;
for(int i=0;i<10;i++)
if(check(rand()%(n-1)+1,n,r,s))
return 0;
return 1;
}
ll rho(ll n,ll c) {
ll k=2,x=rand()%n,y=x,p=1;
for(ll i=1;p==1;i++) {
x=(mul(x,x,n)+c)%n;
p=y>x?y-x:x-y;
p=gcd(n,p);
if(i==k)y=x,k+=k;
}
return p;
}
void solve(ll n) {
if(n==1)return;
if(MR(n)){mx=max(n,mx);return;}
ll t=n;
while(t==n)t=rho(n,rand()%(n-1)+1);
solve(t);
solve(n/t);
}
int main() {
ll x,tmp=0,ans=1;
scanf("%I64d",&x);
while(x!=1){
mx = 0;tmp=0;
solve(x);
while(x%mx==0)x/=mx,++tmp;
ans=ans*(tmp+1);
}
cout << ans << endl;
return 0;
}
G. Extreme Sort
扫一遍
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
int n,a[1055];
int main() {
scanf("%d",&n);
for(int i=1;i<=n;++i) {
scanf("%d",&a[i]);
}
int f=0;
for(int i=2;i<=n;++i) if(a[i-1]>a[i]){puts("no");f=1;break;}
if(!f)puts("yes");
return 0;
}
H. Legacy Code
读题恶心死了的水题
#include <bits/stdc++.h>
#define pb push_back
typedef long long ll;
const int N = 555;
const int M = 2000100;
using namespace std;
vector<int> G[N];
void add(int u,int v) {
G[u].pb(v);
}
int n,m;
string s[N],ts,fid[M];
vector<string> v[N];
int ck(string s) {
string t = "::PROGRAM";
int c=t.size()-1;
for(int i=c,j=s.size()-1;i>=0&&j>=0;--i,--j) {
if(t[i]!=s[j]) return 0;
}
return 1;
}
map<string,int> id;
queue<int> q;
int cnt,vis[N];
void ins(string s) {
if(id.find(s)==id.end()) {
id[s] = ++cnt;
fid[cnt] = s;
if(ck(s)) vis[cnt]=1,q.push(cnt);
}
}
void build() {
for(int i=1;i<=n;++i)
for(int j=0;j<v[i].size();++j){
//add(id[s[i]],id[v[i][j]]);
add(id[v[i][j]],id[s[i]]);
}
}
int solve() {
int ans = 0;
while(!q.empty()) {
int u = q.front(); q.pop();
for(int i=0;i<G[u].size();++i) {
int v=G[u][i];
if(!vis[v]) {
vis[v]=1;
q.push(v);
}
}
}
for(int i=1;i<=cnt;++i)if(!vis[i]&&!ck(fid[i])) ++ans;
return ans;
}
int main() {
scanf("%d", &n);
for(int i=1;i<=n;++i) {
cin >> s[i] >> m;
ins(s[i]);
for(int j=1;j<=m;++j) {
cin >> ts;
v[i].pb(ts);
ins(ts);
}
}
build();
printf("%d
", solve());
return 0;
}
I. Milling machines
水题
#include <bits/stdc++.h>
typedef long long ll;
const int N = 555;
using namespace std;
int w,s,X,Y,mx[N],mp[20000][N];
int cal(int h,int s) {
return min(h,Y-s);
}
int main() {
scanf("%d%d%d%d",&w,&s,&X,&Y);
for(int i=1;i<=w;++i)
for(int j=1;j<=X;++j)
scanf("%d",&mp[i][j]);
for(int i=1;i<=s;++i) {
for(int j=1;j<=X;++j) {int x;
scanf("%d",&x);
mx[j] = max(mx[j],x);
}
}
for(int i=1;i<=w;++i) {int f=0;
for(int j=1;j<=X;++j) {
if(f)printf(" ");f=1;
printf("%d",cal(mp[i][j],mx[j]));
}puts("");
}
return 0;
}
K. Upside down primes
按题意模拟。关键在于判素数，脑残的用了大数素性测试，被卡的。。。然后写了java的用自带的测试，结果更凉。只用测两个数啊，暴力就ok了啊。。。
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
bool isp(ll n) {
for(ll i=2;i*i<=n;i++) {
if(n%i==0) return false;
}
return n!=1;
}
bool isp2(ll x) {
if(x==1)return 0;
if(x%2==0)return 0;
for(ll i=2;i<x;++i)if(x%i==0)return 0;
return 1;
}
int n,M[555];
char s[50];
int ckf() {
for(int i=0;i<n;++i)if(M[s[i]]==-1)return 0;
return 1;
}
ll fan() {
ll ans=0;
reverse(s,s+n);
for(int i=0;i<n;++i){
ll x=M[s[i]];
ans = ans*10LL+x;
}
return ans;
}
int main() {
M['0']=0;M['1']=1;M['2']=2;M['3']=-1;
M['4']=-1;M['5']=5;M['6']=9;M['7']=-1;
M['8']=8;M['9']=6;
scanf(" %s",s);
n=strlen(s);
ll x=0;
for(int i=0;i<n;++i)x=x*10LL+s[i]-'0';
if(!isp(x)) {
printf("no
");
}
else if(!ckf()) {
printf("no
");
}
else {
x = fan();
if(!isp(x)) printf("no
");
else printf("yes
");
}
return 0;
}
总结：被水题场+模板题场干翻我是服气的，下次读完题再开始写。。。英语阅读能力太差了，根本不想看这题。。。