ACM-ICPC 2018 沈阳赛区网络预赛 [菜菜的我！！！]

•  A. Gudako and Ritsuka [博弈动态规划]                                                                                                       题库链接

         通过率: 1.55%

         通过人数: 2

 留坑

•  B. Call of Accepted []                                                                                                                                  题库链接

         通过率: 49.86%

         通过人数: 178

 留坑

•  C. Convex Hull []                                                                                                                                         题库链接

         通过率: 48.59%

         通过人数: 69

 留坑

•  D. Made In Heaven [第k短路]                                                                                                                     题库链接

         通过率: 78.32%

         通过人数: 896

题解：K短路模板题。由于数据均为随机生成,直接预处理出每个点到终点的最短路后A*搜索即可。

/*************************************************************************> File Name: d.cpp> Author: > Mail: > Created Time: 2018年09月08日 星期六 10时43分30秒************************************************************************/
#include<iostream>
#include<cstring>
#include<string.h>
#include<algorithm>
#include<queue> 
#define ll long longusing namespace std;
#define INF 1e9+7
#define MAXN 100010struct node
{ll to;ll val;ll next;
};struct node2
{ll to;ll g,f;bool operator<(const node2 &r ) const  {  if(r.f==f)  return r.g<g;  return r.f<f;  }   
};node edge[MAXN],edge2[MAXN];
ll n,m,s,t,k,e,cnt,cnt2,ans;
ll dis[1010],visit[1010],head[1010],head2[1010];void init()
{memset(head,-1,sizeof(head));memset(head2,-1,sizeof(head2));cnt=cnt2=1;
}void addedge(ll from, ll to, ll val)
{edge[cnt].to=to;edge[cnt].val=val;edge[cnt].next=head[from];head[from]=cnt++;
}void addedge2(ll from,ll to,ll val)
{edge2[cnt2].to=to;edge2[cnt2].val=val;edge2[cnt2].next=head2[from];head2[from]=cnt2++;
}bool spfa(ll s,ll n,ll head[],node edge[],ll dist[])  
{  queue<ll>Q1;  ll inq[1010];  for(int i=0;i<=n;i++)  {  dis[i]=INF;  inq[i]=0;  }  dis[s]=0;  Q1.push(s);  inq[s]++;  while(!Q1.empty())  {  ll q=Q1.front();  Q1.pop();  inq[q]--;  if(inq[q]>n)return false;  ll k=head[q];  while(k>=0)  {  if(dist[edge[k].to]>dist[q]+edge[k].val)  {  dist[edge[k].to]=edge[k].val+dist[q];  if(!inq[edge[k].to])  {  inq[edge[k].to]++;  Q1.push(edge[k].to);  }  }  k=edge[k].next;  }  }  return true;  
}ll A_star(ll s,ll t,ll n,ll k,ll head[],node edge[],ll dist[]) 
{  node2 e,ne;  ll cnt=0;  priority_queue<node2>Q;  if(s==t)k++;  if(dis[s]==INF)  return -1;  e.to=s;  e.g=0;  e.f=e.g+dis[e.to];  Q.push(e);  while(!Q.empty())  {  e=Q.top();  Q.pop();  if(e.to==t)//找到一条最短路径  {  cnt++;  }  if(cnt==k)//找到k短路  {  return e.g;  }  for(ll i=head[e.to]; i!=-1; i=edge[i].next)  {  ne.to=edge[i].to;  ne.g=e.g+edge[i].val;  ne.f=ne.g+dis[ne.to];  Q.push(ne);  }  }  return -1;  
}  
int main()
{//freopen("in.txt", "r", stdin);while(~scanf("%lld%lld",&n,&m)){scanf("%lld%lld%lld%lld",&s,&t,&k,&e);init();for(int i=1;i<=m;i++){ll a, b, c;scanf("%lld%lld%lld",&a,&b,&c);addedge(a,b,c);addedge2(b,a,c);}spfa(t, n, head2, edge2, dis);ans = A_star(s, t, n, k, head, edge, dis);if(ans <= e&&ans != -1) puts("yareyaredawa");else puts("Whitesnake!");}return 0;
} 

•  E. The cake is a lie []                                                                                                                                   题库链接

         通过率: 31.5%

         通过人数: 40

 留坑

•  F. Fantastic Graph [网络流]                                                                                                                         题库链接

         通过率: 82.01%

         通过人数: 383

 留坑

•  G. Spare Tire [容赤]                                                                                                                                    题库链接

         通过率: 55.25%

         通过人数: 500

 留坑

•  H. Hamming Weight []                                                                                                                                 题库链接

         通过率: 7.69%

         通过人数: 1

 留坑

•  I. Lattice's basics in digital electronics [map 模拟]                                                                                      题库链接

         通过率: 86.76%

         通过人数: 531

 留坑

•  J. Ka Chang []                                                                                                                                              题库链接

         通过率: 48.91%

         通过人数: 90

 留坑

• K. Supreme Number [思维，打表 easy]                                                                                                       题库链接

        通过率: 89.03%

        通过人数: 1266

题意：定义supreme number是非空子序列都是素数或者1的数（注意子序列（不连续）与字串（连续）的区别），求不超过的最大的supreme number（）

题解：首先发现数字中只会出现1, 2, 3, 5, 7这5个数字，并且除1可以出现两次之外其他的字符串只能出现一次，而2、5、7三者一定不会有两者同时出现。因此满足条件的整数不会超过四位,全部预处理出来即可(打一个素数表就行啦)。

/*************************************************************************> File Name: k.cpp> Author: howell> Mail: ***> Created Time: 2018年09月08日 星期六 10时43分30秒************************************************************************/#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<string>
#include<vector>
#include<set>
#include<stack>
#define ll long longusing namespace std;
const int maxn = 1e5+7;
const int mod = 1e9+7;int a[30] = {1, 2, 3, 5, 7, 11, 13, 17, 23, 31, 37, 53, 71, 73, 113, 131, 137, 173, 311, 317};
string s;int main()
{//freopen("in.txt", "r", stdin);int t; scanf("%d", &t);int casse = 0;while(t--) {cin >> s;int len = s.length();int j = 0;while(s[j] == '0') j++;printf("Case #%d: ", ++casse);if(len - j >= 5) printf("317\n");else {int ans = 0, t = 1;for(int i = len - 1; i >= j; i--) {ans += (s[i] - '0')*t;t *= 10;}
//            cout << ans << endl;int i = 1;for(; i < 20; i++) if(ans < a[i]) break;printf("%d\n", a[i-1]);}}return 0;
}