目录
20180910沈阳网络赛题解
D. Made In Heaven
MEANING
给出一张有向图，询问S到E的第K短路的长度是否大于T。
SOLUTION
和poj2449一样，A*算法。
CODE
#define IN_PC() freopen("C:\Users\hz\Desktop\in.txt","r",stdin)
#define IN_LB() freopen("C:\Users\acm2018\Desktop\in.txt","r",stdin)
#define OUT_PC() freopen("C:\Users\hz\Desktop\out.txt","w",stdout)
#define OUT_LB() freopen("C:\Users\acm2018\Desktop\out.txt","w",stdout)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 1e3 + 5;
const int MAXE = 1e4 + 5;
const int INF = 0x3f3f3f3f;
struct Graph {
struct edge {
int v,w,nex;
} ed[MAXE];
int tot,head[MAXN];
void addedge(int u,int v,int w) {
tot++;
ed[tot].v = v;
ed[tot].w = w;
ed[tot].nex = head[u];
head[u] = tot;
}
void init() {
tot = 0;
memset(head,0,sizeof head);
}
} G1,G2;
struct node {
int ind,dis;
};
bool operator <(node a,node b) {
return a.dis>b.dis;
}
int d[MAXN];
bool vis[MAXN];
priority_queue<node> q;
void dijkstra(int st,Graph G) {
memset(d,0x3f,sizeof d);
memset(vis,0,sizeof vis);
d[st] = 0;
q.push({st,0});
while(q.size()) {
int u = q.top().ind;
q.pop();
if(vis[u])
continue;
vis[u] = 1;
for(int i = G.head[u]; i; i=G.ed[i].nex) {
int v = G.ed[i].v,w = G.ed[i].w;
if(d[v]>d[u]+w) {
d[v] = d[u]+w;
q.push({v,d[v]});
}
}
}
}
struct anode {
int to;
int f,g;
bool operator < (const anode &t) const {
if(t.f==f)
return t.g < g;
return t.f < f;
}
};
int Astar(int st,int et,int k) {
int cnt = 0;
priority_queue<anode> pq;
if(st==et)
k++;
if(d[st] == INF)
return -1;
pq.push({st,d[st],0});
while(pq.size()){
anode u = pq.top();
if(u.g>100000000)return -1;
pq.pop();
if(u.to==et)cnt++;
if(cnt==k)return u.g;
for(int i = G1.head[u.to];i;i=G1.ed[i].nex){
anode v;
v.to = G1.ed[i].v;
v.g = u.g + G1.ed[i].w;
v.f = v.g + d[v.to];
pq.push(v);
}
}
return -1;
}
int main() {
// IN_LB();
int n,m;
while(scanf("%d%d",&n,&m)!=EOF) {
int st,et,k,t;
scanf("%d%d%d%d",&st,&et,&k,&t);
G1.init();
G2.init();
for(int i=0; i<m; i++) {
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
G1.addedge(u,v,w);
G2.addedge(v,u,w);
}
dijkstra(et,G2);//在反图上跑Dijkstra
int ans = Astar(st,et,k);//在正图上跑Astar
if(ans!=-1&&ans<=t)printf("yareyaredawa
");
else printf("Whitesnake!
");
}
return 0;
}
F. Fantastic Graph
MEANING
给一个二分图，询问能否找到一种匹配，使得每个点相连的匹配边数在[L,R]内。
SOLUTION
解法一（官方题解）：有源汇的上下界网络流的可行流问题。
解法二：Dinic算法跑二分图多重匹配。先令左部图的点取流量上界（超级源点与左部图各点连一条容量为R的边），右部图的点取流量下界（超级汇点与右部图各点连一条容量为L的边）,跑最大流。
然后令右部图的点取流量上界（超级源点与右部图各点连一条容量为R的边），左部图的点取流量下界（超级汇点与左部图各点连一条容量为L的边），再跑一边最大流。如果两次与汇点相连的边都跑满流量，说明可行，否则不可行。
CODE
G. Spare Tire
CODE
队友代码
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long ll;
const int mod=1e9+7;
const int maxn = 10050;
ll prime[maxn];
ll isCon[maxn];
ll cnt = 0;
void eurla(){
for (int i=2;i<maxn;i++){
if (isCon[i]==0) {
prime[cnt++] = i;
// cout<<i<<endl;
}
for (int j=0;j<cnt&&i*prime[j]<maxn;j++){
isCon[ i*prime[j] ] = 1;
if (i%prime[j]==0) break;
}
}
}
ll qpow(ll a,ll x){
ll ret = 1;
while(x){
if (x&1) ret=ret*a%mod;
a=a*a%mod;
x>>=1;
}
return ret;
}
ll a[15];
int main()
{
eurla();
ll inv,inv2;
inv = qpow(6,mod-2);
inv2 = qpow(2,mod-2);
ll k,m;
while(~scanf("%lld %lld",&k,&m))
{
ll p = m;
ll cntt=0;
for(int i=0;i<cnt;i++)
{
if(p<prime[i])
break;
if (p%prime[i]==0){
a[cntt++] = prime[i];
while (p%prime[i]==0)
p = p/prime[i];
}
}
if (p!=1) a[cntt++] = p;
// for (int i=0;i<cntt;i++){
// cout<<a[i]<<" ";
// }cout<<endl;
ll ans=0;
for(int i=1;i<(1<<cntt);i++)
{
ll x=0,y=1;
for(int j=0;j<cntt;j++)
{
if((i>>j)&1)
{
x++;
y = y*a[j]%mod;
}
}
// printf("%lld
",y);
ll n = k/y;
if(x%2)
ans = (ans+y*y%mod*n%mod*(n+1)%mod*(2*n+1)%mod*inv%mod+y*n*(n+1)%mod*inv2%mod+mod)%mod;
else
ans = (ans-y*y%mod*n%mod*(n+1)%mod*(2*n+1)%mod*inv%mod-y*n*(n+1)%mod*inv2%mod+mod)%mod;
}
ll s;
s = k*(k+1)%mod*(2*k+1)%mod*inv%mod+k*(k+1)%mod*inv2%mod;
// printf("%lld
",ans);
ans = (s-ans+mod)%mod;
printf("%lld
",ans);
}
return 0;
}
I. Lattice's basics in digital electronics
按题意模拟即可。
CODE
队友代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
const ll maxn = 2000006;
const ll mod = 1000000007;
const ll trieNum = 5010;
struct Decoder {
struct Trie {
int isEnd;
int nxt[2];
int val;
} trie[trieNum];
int root = 0;
int cnt = 0;
void init() {
root =cnt = 0;
memset(trie,0,sizeof trie );
}
void insert(char s[],int val) {
int p = root;
int i=0;
for (; s[i]; i++) {
int j = s[i]-'0';
if (trie[p].nxt[j]==0 ) {
trie[p].nxt[j] = ++cnt;
}
p = trie[p].nxt[j];
}
trie[p].isEnd = 1;
trie[p].val = val ;
}
void decode(char s[],char d[]) {
int i=0;
int tot = 0;
int p = root;
for (; s[i]; i++) {
p = trie[p].nxt[s[i]-'0'];
if (trie[p].isEnd==1) {
d[tot++] = trie[p].val ;
p=root;
}
}
d[tot] = ' ';
}
} decoder;
void x2b(char s[],char d[],int len) {
for (int i=0; i<len; i++) {
int v;
if (isdigit(s[i]))
v = s[i]-'0';
else
v = s[i]-'A'+10;
for (int j=0; j<4; j++) {
d[i*4 + 3 - j ] = ((v>>j)&1)+'0' ;
}
}
d[len*4] = ' ';
}
void detect(char s[],char d[],int len) {
int tot = 0;
for (int i=0; (i+1)*9<=len; i++) {
int k = 0;
for (int j=0; j<9; j++) {
if (s[ i*9 + j ]== '1' )
k++;
}
if (k%2) {
for (int j=0; j<8; j++) {
d[tot++] = s[i*9+j];
}
}
}
d[tot]=' ';
}
char s1[maxn],s2[maxn],s3[maxn],tmp[200];
int main() {
// freopen("in.txt","r",stdin);
int t;
scanf("%d",&t);
while(t--) {
int n,m;
scanf("%d%d",&m,&n);
decoder.init();
for (int i=1; i<=n; i++) {
int val;
scanf("%d",&val);
scanf("%s",tmp);
decoder.insert(tmp,val);
}
scanf("%s",s1);
int len = strlen(s1);
x2b(s1,s2,len);
detect(s2,s1,len*4);
decoder.decode(s1,s3);
for (int i=0; i<m; i++) {
printf("%c",s3[i]);
}
printf("
");
}
return 0;
}
K. Supreme Number
签到题。就看谁找素数速度更快了。现在纸上枚举1，2，3，5，7的可能组合，可以肯定不会超过四位。对于无法判断是否素数的，写程序暴力判即可。