ACM-ICPC 2018 沈阳赛区网络预赛 D A*算法 F 有上下界的网络流 G分解质因数+公式 容斥 I 模拟 K讨论

D
题意：找是否存在第k短路且判断长度是否小于等于T。
思路：A*算法裸题。

#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
using namespace std;
const int AX = 1e5+66;
const int MAXN = 1e4+66;
int n , m , k;
int s ,t ;
int tot ;
int retot ;
struct edge{int to , w ;int next1;
}G[AX] , RG[AX];
//f = g + h 
struct Node{int v;int f , h , g;bool operator < ( const Node &a ) const{if( f == a.f ){return g > a.g;}return f > a.f;}
};int dis[MAXN];
int head[MAXN];
int rehead[AX];
int vis[MAXN];
void addedge( int u , int v , int c ){G[tot].to = v;G[tot].w = c;G[tot].next1 = head[u];head[u] = tot++;RG[retot].to = u;RG[retot].w = c;RG[retot].next1 = rehead[v];rehead[v] = retot ++;
}
void SPFA(){for( int i = 1 ; i <= n ; i++ ){dis[i] = INF;}   dis[t] = 0;queue<int>Q;Q.push(t);while( !Q.empty() ){int u = Q.front();Q.pop();for( int i = rehead[u] ; ~i ; i = RG[i].next1 ){int v = RG[i].to ;int w = RG[i].w ;if( dis[v] > dis[u] + w ){dis[v] = dis[u] + w;Q.push(v);}}}   
}int Astar( Node a ){memset( vis , 0 ,sizeof(vis) );if( dis[s] == INF ) return -1;if( s == t ) k++;priority_queue<Node>Q;Q.push(a);while( !Q.empty() ){Node tmp = Q.top();Q.pop();int v = tmp.v;vis[v] ++ ;if( vis[t] == k ) return tmp.g;for( int i = head[v] ; ~i ; i = G[i].next1 ){Node p;p.v = G[i].to;p.h = dis[G[i].to];p.g = tmp.g + G[i].w;p.f = p.g + p.h;Q.push(p);}}return -1;
}int main(){int T;while( ~scanf("%d%d",&n,&m) ){scanf("%d%d%d%d",&s,&t,&k,&T);tot = 0 ;retot = 0;memset( head , -1 , sizeof(head) );memset( rehead , -1 , sizeof(rehead) );int x , y , w ;for( int i = 0 ; i < m ; i++ ){scanf("%d%d%d",&x,&y,&w);addedge( x , y , w );}SPFA();Node a;a.v = s ;a.g = 0;a.h = dis[s];a.f = a.g + a.h;int g = Astar(a);//printf("%d\n",g);if( g != -1 && g <= T ){printf("yareyaredawa\n");}else{printf("Whitesnake!\n");}} return 0 ;
}

F
思路：有源汇有上下界的网络流。限制是ss到每个点流量为[L,R]，每个点到tt为[L,R]。
Code：

#include <bits/stdc++.h>
#define LL long long 
#define INF 0x3f3f3f3f
using namespace std;
const int AX = 1e5+66;int n , m ;
int sp , tp ;
int ss, tt ; 
int head[AX];
int d[AX];
int cur[AX];
int tot;struct Node{int u , v , flow , next1 ; Node( int u = 0 , int v = 0 , int flow = 0 , int next1 = 0 ):u(u),v(v),flow(flow),next1(next1){}
}G[20*AX];void addedge(int u,int v,int flow){G[tot] = Node( u , v , flow , head[u] ) ; head[u] = tot++ ;G[tot] = Node( v , u , 0 , head[v] ) ; head[v] = tot++ ;
}bool bfs( ){memset( d, -1 , sizeof(d) );d[sp] = 0 ;queue<int>q ;q.push( sp ) ;while( !q.empty() ){int u = q.front() ; q.pop();for( int i = head[u] ; ~i ; i = G[i].next1 ){int v = G[i].v ; if( d[v] == -1 && G[i].flow ) {d[v] = d[u] + 1 ;q.push(v) ;if( v == tp ) return true ; }}} return ~d[tp];
}int dfs( int u , int cap ){if( u == tp ) return cap ; int r = 0 ;for( int i = cur[u] ; ~i ; i = G[i].next1) {int v = G[i].v ; if( G[i].flow && d[v] == d[u] + 1 ){int tmp = min( G[i].flow , cap - r );cur[u] = i ;tmp = dfs(v,tmp);r += tmp ; G[i].flow -= tmp ;G[i^1].flow += tmp ; if( r == cap ) break;}}if( !r ) d[u] -= 2 ;return r ; 
}int Dinic( ){int cnt = 0 ;int t ;while( bfs() ){memcpy(cur,head,sizeof(head));while( t = dfs( sp, INF ) ) cnt += t ; }return cnt ; 
}int main(){int k , L , R ;int Case = 0 ;while( ~scanf("%d%d%d",&n,&m,&k) ){tot = 0 ;memset( head , -1 , sizeof(head) );sp = n + m + 1 ;  tp = n + m + 2 ; ss = n + m + 3 ;  tt = n + m + 4 ;scanf("%d%d",&L,&R);int u , v ; for( int i = 0 ; i < k ; i++ ){scanf("%d%d",&u,&v);addedge( u , v + n , 1 );}for( int i = 1 ; i <= n ; i++ ){addedge( ss , i , R - L ) ;addedge( sp , i , L ) ;addedge( ss , tp , L ) ;}for( int i = 1;  i <= m ; i++ ){addedge( i + n , tt , R - L ) ;addedge( sp , tt , L ) ;addedge( i + n , tp , L ) ;}addedge( tt , ss , INF ) ;printf("Case %d: ",++Case);if( Dinic() == ( n + m ) * L ) puts("Yes");else puts("No");}return 0 ; 
}

G
题意：an = n * n+n，求

思路：可以转化成

套容斥可以求得结果。
另：
Code：

#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
#define LL long long 
using namespace std;
const LL MOD = 1e9 + 7 ;
const int AX = 1e5 + 666 ;
const LL inv2 = 500000004;
const LL inv6 = 166666668;
LL m , n ;LL cal( LL n , LL x ){LL num = n / x ; return ( num * ( num + 1 ) %MOD * ( 2 * num + 1 )%MOD * inv6%MOD * x %MOD* x % MOD + num * ( num + 1 )%MOD * inv2 %MOD * x%MOD )%MOD ;
}
int fac[AX];
int tot ;void getFac( ){tot = 0 ;for( int i = 2 ; i * i <= m ; i++ ){if( ( m % i ) == 0 ){fac[tot++] = i ; while( m % i == 0 ) m /= i ;}}if( m > 1 ) fac[tot++] = m ;
}int main(){while( ~scanf("%d%d",&n,&m) ){getFac();LL ans = cal( n , 1 ) ;LL res = 0LL ;for( int i = 1 ; i < ( 1 << tot ) ; i++ ){int f = 0 ; LL tmp = 1LL ;int num = 0 ;for( int j = 0 ; j < tot ; j++ ){if( ( 1 << j ) & i ){tmp = tmp * fac[j] % MOD ;num ++ ;}}tmp = cal( n , tmp );if( num % 2 ){res = ( res + tmp % MOD ) % MOD;}else{res = ( res + MOD - tmp ) % MOD ;}}printf("%lld\n",(ans+MOD-res)%MOD);}return 0 ;
}

I
思路：模拟，16进制转2进制，然后奇偶校验，然后根据映射得出结果。
Code：

#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
#define LL long long 
using namespace std;
map<char,string> mp; 
map<string , int > mp1; 
void init(){mp['0'] ="0000"; mp['1']="0001";mp['2']="0010";mp['3']="0011";mp['4']="0100";mp['5']="0101";mp['6']="0110";mp['7']="0111";mp['8']="1000";mp['9']="1001";mp['A']="1010";mp['B']="1011";mp['C']="1100";mp['D']="1101";mp['E']="1110";mp['F']="1111";mp['a']="1010";mp['b']="1011";mp['c']="1100";mp['d']="1101";mp['e']="1110";mp['f']="1111";
}
int main(){int T;init();ios_base::sync_with_stdio(false);cin.tie(0) ; cout.tie(0) ; cin >> T;int m , n ; while( T-- ){string a; string b; string c; cin >> m >> n ; mp1.clear();int asc ;string s ;  for( int i = 0 ; i < n ; i++ ){cin >> asc >> s ; mp1[s] = asc ; }b = "";cin >> a ; int len = a.size();for( int i = 0 ; i < len ; i++ ){b += mp[a[i]];}len = b.size();for( int i = 0 ; i + 8 < len ; i += 9 ){int num = 0 ; string tmp = "" ;int j ; for( j = i ; j < i + 8 ; j++ ){if( b[j] == '1' ){num ++ ; }tmp += b[j] ; }if( num % 2 ){if( b[j] == '0' ) c += tmp ; }else{if( b[j] == '1' ) c += tmp ; }}int size = c.size() ; string tmp = "" ; string res = "" ;int length = 0 ;for( int i = 0 ; i < size ; i ++ ){tmp += c[i] ; if( length == m ) break ; if( mp1[tmp] ){//cout << (char)mp1[tmp];res += (char)mp1[tmp];length ++ ;tmp = "";}}cout << res << endl;}   return 0 ;
}

K
题意：一个数为素数且任意子串为素数
思路：考虑到答案中任意一位都必须是1或质数，可知答案只可能由1、2、3、5、7构成。由于任意两个不为1的数字构成 的两位数一定可以被11整除，所以答案中除1外的数字只能出现一次；1最多出现2次，因为111可以被3整除；而 2、5、7三者一定不会有两者同时出现。因此满足条件的整数不会超过四位，全部预处理出来即可。
Code:

#include <bits/stdc++.h>
using namespace std;int a[21]={1,2,3,5,7,11,13,17,23,31,37,53,71,73,113,131,137,173,311,317,10000};int init(string s){int cnt = 0;for(int i=0;i<s.length();i++){cnt = cnt*10 + s[i]-'0';}return cnt;
}
int t;
int main(){cin>>t;for(int i=1;i<=t;i++){string s;cin>>s;cout<<"Case #"<<i<<": ";if(s.length()>=4){cout<<"317"<<endl;}else{int ans = init(s);for(int i=0;i<21;i++){if(a[i]>ans){cout<<a[i-1]<<endl;break;}}}}return 0;
}