本文的目的是介绍2017Android和iOS频频被曝Bug，它们都怎么了？的详细情况，特别关注2017安卓的相关信息。我们将通过专业的研究、有关数据的分析等多种方式，为您呈现一个全面的了解2017A
本文的目的是介绍2017 Android 和 iOS 频频被曝 Bug，它们都怎么了？的详细情况，特别关注2017安卓的相关信息。我们将通过专业的研究、有关数据的分析等多种方式，为您呈现一个全面的了解2017 Android 和 iOS 频频被曝 Bug，它们都怎么了？的机会，同时也不会遗漏关于(寒假开黑gym)2017-2018 ACM-ICPC German Collegiate Programming Contest (GCPC 2017)、2017-2018 ACM-ICPC German Collegiate Programming Contest (GCPC 2017)、2017-2018 ACM-ICPC German Collegiate Programming Contest (GCPC 2017) Solution、2017-2018 ACM-ICPC Nordic Collegiate Programming Contest (NCPC 2017) D bfs 思维 E bfs I Floyd 找最小环...的知识。
本文目录一览：- 2017 Android 和 iOS 频频被曝 Bug，它们都怎么了？（2017安卓）
- (寒假开黑gym)2017-2018 ACM-ICPC German Collegiate Programming Contest (GCPC 2017)
- 2017-2018 ACM-ICPC German Collegiate Programming Contest (GCPC 2017)
- 2017-2018 ACM-ICPC German Collegiate Programming Contest (GCPC 2017) Solution
- 2017-2018 ACM-ICPC Nordic Collegiate Programming Contest (NCPC 2017) D bfs 思维 E bfs I Floyd 找最小环...
2017 Android 和 iOS 频频被曝 Bug，它们都怎么了？（2017安卓）
虽然很多采用 Android 系统的厂商还未更新 8.0 系统，但谷歌已经开始为自家支持的 Pixel 设备推送最新的 Android 8.1 了。上周，Android 8.1 系统刚刚在谷歌 Pixel 设备上推送发布。但随后用户就发现了 Android 8.1 系统存在的严重 Bug，直接影响到了他们使用手机的体验。
更新 Android 8.1 之后，就有 Pixel C 平板用户反映升级后竟然自动恢复出厂设置，所有数据都被擦除。
随后，大量用户在 Google 论坛、Reddit 论坛中反馈，称在 Android 8.1 下出现了严重的多点触控失效问题。这个问题说严重点就是，会直接影响到用户在多场景方面的操作。尤其玩游戏时，特别是 FPS 射击游戏，因为需要同时使用多根手指操作，这一 Bug 最为明显，直接导致画面出现严重的跳跃、抖动现象，无法进行游戏。
Pixel 用户社区管理员 Oririn 针对用户反馈的问题正式作出回应：“正在就此进行调查，并希望碰到 Bug 的用户及时反馈。”
联想到今年早些时候 Android 8.0 曝出的开启 WiFi 仍会使用数据、蓝牙连接错误、导致 OLED 烧屏等 Bug，以及同为难兄难弟，被曝出触摸屏失灵、摄像头无法对焦、无限重启、Face ID 启动失败、HomeKit 安全漏洞等问题的 iOS 11，不禁让一些网友吐槽：“iOS 和 Android ，2017 年都怎么了？”
(寒假开黑gym)2017-2018 ACM-ICPC German Collegiate Programming Contest (GCPC 2017)
<a href="https://codeforces.com/gym/101933/" target="_blank"><strong>传送门</strong></a>
付队！
许老师！
B.Buildings （polya定理）
题意
B：给你m面墙，每面墙是n*n的格子，你有c种颜色，问你有多少种涂色方案。用polya定理
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
const int maxn=3e5+50;
const ll inf=0x3f3f3f3f3f3f3f3fLL;
///a<mod 并且 p为素数
ll pow_mod(ll x, ll n, ll mod){
ll res=1;
while(n){
if(n&1)res=res*x%mod;
x=x*x%mod;
n>>=1;
}
return res;
}
ll inv(ll a,ll p){return pow_mod(a,p-2,p);}
int main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
int n,m,c;
cin>>n>>m>>c;
ll ans=0;
for(int i=0;i<m;i++){
ans+=pow_mod(c,n*n*__gcd(i,m),mod);
ans%=mod;
}
cout<<ans*inv(m,mod)%mod<<endl;
return 0;
}
C.Joyride （分层图最短路）
题意
C：游乐场有n个设施，有m条人行道，游乐设施会花费ti的时间和pi的钱，人行道需要花费t的时间，你需要用最少的钱恰好游玩x的时间，起点是1，终点是1，求最少的钱是多少4
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=998244353;
const int maxn=1e3+50;
const int inf=1e9+7;
int x,n,m,t;
vector<int>ve[maxn];
struct need{
int t,p;
}ned[maxn];
struct node{
int in;
int w;
int time;
};
int dis[maxn][maxn];
void dij(){
queue<node>q;
q.push(node{1,ned[1].p,ned[1].t});
for(int i=0;i<=1000;i++){
for(int j=0;j<=1000;j++)dis[i][j]=inf;
}
dis[1][ned[1].t]=ned[1].p;
while(!q.empty()){
node now=q.front();
q.pop();
int in=now.in,w=now.w,time=now.time;
if(time+ned[in].t<=x&&w+ned[in].p<dis[in][time+ned[in].t]){
dis[in][time+ned[in].t]=w+ned[in].p;
q.push(node{in,dis[in][time+ned[in].t],time+ned[in].t});
}
for(int i=0;i<ve[in].size();i++){
int nex=ve[in][i];
int nextime=time+t+ned[nex].t;
if(nextime<=x&&dis[nex][nextime]>w+ned[nex].p){
dis[nex][nextime]=w+ned[nex].p;
q.push(node{nex,w+ned[nex].p,nextime});
}
}
}
}
int main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
cin>>x>>n>>m>>t;
for(int i=1;i<=m;i++){
int a,b;
cin>>a>>b;
ve[a].push_back(b);
ve[b].push_back(a);
}
for(int i=1;i<=n;i++){
cin>>ned[i].t>>ned[i].p;
}
dij();
if(dis[1][x]==inf)cout<<"It is a trap."<<endl;
else cout<<dis[1][x]<<endl;
return 0;
}
D.Pants On Fire (map+dfs,or 传递闭包)
题意
D 有n个已知串，给m个串，让你去判断他们是对的还是错的还是未知的
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=998244353;
const int maxn=1e3+50;
const int inf=1e9+7;
map<string,int>mp;
int cnt;
bool ok[500][500];
int main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
string a,b,c,d,e;
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>a>>b>>c>>d>>e;
if(!mp[a])mp[a]=++cnt;
if(!mp[e])mp[e]=++cnt;
ok[mp[a]][mp[e]]=true;
}
for(int k=1;k<=cnt;k++){
for(int i=1;i<=cnt;i++){
for(int j=1;j<=cnt;j++){
ok[i][j]|=ok[i][k]&&ok[k][j];
}
}
}
for(int i=1;i<=m;i++){
cin>>a>>b>>c>>d>>e;
if(!mp[a]||!mp[e]){cout<<"Pants on Fire"<<endl;continue;}
int u=mp[a],v=mp[e];
if(ok[u][v])cout<<"Fact"<<endl;
else if(ok[v][u])cout<<"Alternative Fact"<<endl;
else{
cout<<"Pants on Fire"<<endl;
}
}
return 0;
}
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=998244353;
const int maxn=1e3+50;
const int inf=1e9+7;
map<string,int>mp;
int cnt;
vector<int>G[maxn];
bool dfs(int u,int v){
for(int i=0;i<G[u].size();i++){
if(G[u][i]==v)return true;
bool ok=dfs(G[u][i],v);
if(ok)return true;
}
return false;
}
int main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
string a,b,c,d,e;
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>a>>b>>c>>d>>e;
if(!mp[a])mp[a]=++cnt;
if(!mp[e])mp[e]=++cnt;
G[mp[a]].push_back(mp[e]);
}
for(int i=1;i<=m;i++){
cin>>a>>b>>c>>d>>e;
if(!mp[a]||!mp[e]){cout<<"Pants on Fire"<<endl;continue;}
int u=mp[a],v=mp[e];
if(dfs(u,v))cout<<"Fact"<<endl;
else if(dfs(v,u))cout<<"Alternative Fact"<<endl;
else{
cout<<"Pants on Fire"<<endl;
}
}
return 0;
}
F.Plug It In (匈牙利算法/二分图匹配/网络流)
题意
m个插口，n个电器 k个可以匹配的连接 ,问你最大匹配数，但是你有一次机会把一个接口变成三个一样的
思路
考虑暴力每次暴力把一个其中一个接口数+2跑匈牙利算法，复杂度N^3，然后发现其实第一次跑的最初的图是可以一直重复利用的，然后就直接把后面的多出来的接口拿去跑增广路就行。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
const int maxn=3e5+50;
const ll inf=0x3f3f3f3f3f3f3f3fLL;
/// 二分图最大基数匹配
int mp[1550][1550];
int link[1550];
int n,m,k;
bool vis[1550];
int remain[1550];
bool match(int u){
for(int i=1;i<=m;i++){
if(vis[i]==0&&mp[u][i]){
vis[i]=1;
if(link[i]==-1||match(link[i])){
link[i]=u;
return 1;
}
}
}
return 0;
}
int main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
int k;
cin>>n>>m>>k;
memset(link,-1,sizeof(link));
for(int i=1;i<=k;i++){
int a,b;
cin>>a>>b;
mp[a][b]=1;
}
int ans=0;
for(int i=1;i<=n;i++){
memset(vis,0,sizeof(vis));
if(match(i))ans++;
}
for(int i=1;i<=m;i++){
remain[i]=link[i];
}
int mx=0;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++)mp[n+1][j]=mp[n+2][j]=mp[i][j];
for(int i=1;i<=m;i++){
link[i]=remain[i];
}
int now=0;
memset(vis,0,sizeof(vis));
for(int j=n+1;j<=n+2;j++){
if(match(j))now++;
}
mx=max(now,mx);
}
cout<<ans+mx<<endl;
return 0;
}
G.Water Testing (皮克定理)
题意
给你一个多边形问你多边形中的整点个数有多少
思路
皮克定理
皮克定理是指一个计算点阵中顶点在格点上的多边形面积公式，该公式可以表示为2S=2a+b-2，其中a表示多边形内部的点数，b表示多边形边界上的点数，S表示多边形的面积。
其中，面积用每两条线的叉积计算
当O点为原点时，根据向量的叉积计算公式，各个三角形的面积计算如下：
S_OAB = 0.5*(A_xB_y - A_yB_x) 【(A_x，A_y)为A点的坐标】
S_OBC = 0.5*(B_xC_y - B_yC_x)
S_OCD = 0.5*(C_xD_y - C_yD_x)
S_ODE = 0.5*(D_xE_y - D_yE_x)
S_OEA = 0.5*(E_xA_y - E_yA_x)
边界的点数用gcd(a.x-b.x,a.y-b.y)计算
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=998244353;
const int maxn=3e5+50;
const ll inf=0x3f3f3f3f3f3f3f3fLL;
struct Point{
ll x,y;
}my[maxn];
int main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
int n;
cin>>n;
for(int i=0;i<n;i++){
cin>>my[i].x>>my[i].y;
}
ll s=0,b=0;
for(int i=0;i<n;i++){
s+=my[i].x*my[(i+1)%n].y-my[(i+1)%n].x*my[i].y;
b+=__gcd(abs(my[i].x-my[(i+1)%n].x),abs(my[i].y-my[(i+1)%n].y));
}
s/=2;
s=abs(s);
cout<<s-b/2+1<<endl;
return 0;
}
I.Uberwatch (基础DP)
思路
对于每个点考虑两种情况，如果他不放必杀技那 $$ dp[i]=dp[i-1] $$ 如果他放必杀技，那么他就只能在i-m时间之前放的最大值加起来 $$ dp[i]=dp[i-m]+a[i] $$
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=998244353;
const int maxn=3e5+50;
const ll inf=0x3f3f3f3f3f3f3f3fLL;
int a[maxn];
int dp[maxn];
int main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>a[i];
}
int sum=0;
for(int i=m+1;i<=n;i++){
dp[i]=max(dp[i-1],dp[i-m]+a[i]);
}
cout<<dp[n]<<endl;
return 0;
}
K.You Are Fired (签到)
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=998244353;
const int maxn=1e5+50;
const ll inf=0x3f3f3f3f3f3f3f3fLL;
struct node{
ll money;
string name;
}my[maxn];
bool vis[maxn];
int main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
ll n,d,k;
cin>>n>>d>>k;
for(int i=1;i<=n;i++){
cin>>my[i].name>>my[i].money;
}
sort(my+1,my+1+n,[](node a,node b){
return a.money>b.money;
});
ll ans=0,num=0;
for(int i=1;i<=k;i++){
ans+=my[i].money;
vis[i]=true;
num++;
if(ans>=d)break;
}
if(ans<d)cout<<"impossible"<<endl;
else{
cout<<num<<endl;
for(int i=1;i<=n;i++){
if(vis[i])
cout<<my[i].name<<", YOU ARE FIRED!"<<endl;
}
}
return 0;
}
2017-2018 ACM-ICPC German Collegiate Programming Contest (GCPC 2017)
A Drawing Borders
很多构造方法，下图可能是最简单的了
代码：
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+10;
struct Point{ int x,y; };
Point a[maxn]; int numa=0;
Point b[maxn]; int numb=0;
vector<pair<double,double> > va;
vector<pair<double,double> > vb;
void checka()
{
va.push_back({3000,3000});
va.push_back({3000,2999});
for(int i=numa;i>=1;i--)
{
va.push_back( { a[i].x*1.000-0.3,2999} );
va.push_back( { a[i].x*1.000-0.3,a[i].y*1.000+0.1} );
va.push_back( { a[i].x*1.000+0.1,a[i].y*1.000+0.1} );
va.push_back( { a[i].x*1.000+0.1,a[i].y*1.000-0.1} );
va.push_back( { a[i].x*1.000-0.3,a[i].y*1.000-0.1} );
while(i-1>=1 && a[i-1].x==a[i].x)
{
i--;
va.push_back( { a[i].x*1.000-0.3,a[i].y*1.000+0.1} );
va.push_back( { a[i].x*1.000+0.1,a[i].y*1.000+0.1} );
va.push_back( { a[i].x*1.000+0.1,a[i].y*1.000-0.1} );
va.push_back( { a[i].x*1.000-0.3,a[i].y*1.000-0.1} );
}
va.push_back( {a[i].x*1.0000-0.3,-1200} );
va.push_back( {a[i].x*1.0000-0.39,-1200} );
va.push_back( {a[i].x*1.0000-0.39,2999});
}
va.push_back({-3000,2999});
va.push_back({-3000,3000});
}
void checkb()
{
vb.push_back({-3000,-3000});
vb.push_back({-3000,-2999});
for(int i=1;i<=numb;i++)
{
vb.push_back( { b[i].x*1.000+0.3,-2999} );
vb.push_back( { b[i].x*1.000+0.3,b[i].y*1.000-0.1} );
vb.push_back( { b[i].x*1.000-0.1,b[i].y*1.000-0.1} );
vb.push_back( { b[i].x*1.000-0.1,b[i].y*1.000+0.1} );
vb.push_back( { b[i].x*1.000+0.3,b[i].y*1.000+0.1} );
while(i+1<=numb && b[i+1].x==b[i].x)
{
i++;
vb.push_back( { b[i].x*1.000+0.3,b[i].y*1.000-0.1} );
vb.push_back( { b[i].x*1.000-0.1,b[i].y*1.000-0.1} );
vb.push_back( { b[i].x*1.000-0.1,b[i].y*1.000+0.1} );
vb.push_back( { b[i].x*1.000+0.3,b[i].y*1.000+0.1} );
}
vb.push_back( { b[i].x*1.000+0.3,1200} );
vb.push_back( { b[i].x*1.000+0.39,1200} );
vb.push_back( { b[i].x*1.000+0.39,-2999} );
}
vb.push_back({3000,-2999});
vb.push_back({3000,-3000});
}
bool upa(Point a,Point b){if(a.x==b.x) return a.y<b.y;return a.x<b.x;}
bool upb(Point a,Point b){if(a.x==b.x) return a.y<b.y;return a.x<b.x;}
int main()
{
int n ; scanf("%d",&n);
for(int i=1;i<=n;i++)
{
int x,y,z; scanf("%d %d %d",&x,&y,&z);
if(z==1) a[++numa].x=x,a[numa].y=y;
if(z==2) b[++numb].x=x,b[numb].y=y;
}
sort(a+1,a+1+numa,upa); checka();
sort(b+1,b+1+numb,upb); checkb();
printf("%d\n",va.size()); for(int i=0;i<va.size();i++) printf("%.4f %.4f\n",va[i].first,va[i].second);
printf("%d\n",vb.size()); for(int i=0;i<vb.size();i++) printf("%.4f %.4f\n",vb[i].first,vb[i].second);
}B Buildings
polya定理
代码：
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int mod=1e9+7;
int quick(int a,int n)
{
int ans=1;
while(n)
{
if(n%2==0) {a=a%mod*a%mod;n=n/2; }
else {ans=ans%mod*a%mod; n--; }
}
return ans;
}
int p[500+10];
int32_t main()
{
int n,m,c; cin>>n>>m>>c;// m temp;
int temp=quick(c,n*n); //cout<<temp<<endl;
p[0]=1;
for(int i=1;i<= m;i++) p[i]=p[i-1]%mod*temp%mod;
int a=0;
for(int i=0;i<m;i++) a+=p[__gcd(i,m)],a=a%mod;
int ans=a*quick(m,mod-2)%mod;
cout<<ans<<endl;
}C Joyride
dp + 记忆化搜索
代码：
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize(4)
#include<bits/stdc++.h>
using namespace std;
#define y1 y11
#define fi first
#define se second
#define pi acos(-1.0)
#define LL long long
//#define mp make_pair
#define pb push_back
#define ls rt<<1, l, m
#define rs rt<<1|1, m+1, r
#define ULL unsigned LL
#define pll pair<LL, LL>
#define pli pair<LL, int>
#define pii pair<int, int>
#define piii pair<pii, int>
#define pdd pair<double, double>
#define mem(a, b) memset(a, b, sizeof(a))
#define debug(x) cerr << #x << " = " << x << "\n";
#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
//head
const int N = 1e3 + 10;
const LL INF = 0x3f3f3f3f3f3f3f3f;
LL dp[N][N];
vector<int> g[N];
int x, n, m, T, u, v;
int t[N], p[N];
LL dfs(int u, int m) {
if(m > x) return INF;
if(~dp[u][m]) return dp[u][m];
if(u == 1 && m == x) return dp[u][m] = 0;
dp[u][m] = INF;
for (int v : g[u]) {
dp[u][m] = min(dp[u][m], dfs(v, m+T+t[v]) + p[v]);
}
dp[u][m] = min(dp[u][m], dfs(u, m+t[u])+p[u]);
return dp[u][m];
}
int main() {
mem(dp, -1);
scanf("%d", &x);
scanf("%d %d %d", &n, &m, &T);
for (int i = 1; i <= m; ++i) scanf("%d %d", &u, &v), g[u].pb(v), g[v].pb(u);
for (int i = 1; i <= n; ++i) scanf("%d %d", &t[i], &p[i]);
LL tmp = dfs(1, t[1]) + p[1];
if(t[1]*2 > x || tmp >= INF) printf("It is a trap.\n");
else printf("%lld\n", tmp);
return 0;
}D Pants On Fire
拓扑排序
代码：
#include <algorithm>
#include <iterator>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <iomanip>
#include <bitset>
#include <cctype>
#include <cstdio>
#include <string>
#include <vector>
#include <stack>
#include <cmath>
#include <queue>
#include <list>
#include <map>
#include <set>
#include <cassert>
/*
⊂_ヽ
＼＼ Λ＿Λ 来了老弟
＼(''ㅅ'')
> ⌒ヽ
/ へ＼
/ / ＼＼
ﾚ ノ ヽ_つ
/ /
/ /|
( (ヽ
| |、＼
| 丿 ＼ ⌒)
| | ) /
''ノ ) Lﾉ
*/
using namespace std;
#define lson (l , mid , rt << 1)
#define rson (mid + 1 , r , rt << 1 | 1)
#define debug(x) cerr << #x << " = " << x << "\n";
#define pb push_back
#define pq priority_queue
typedef long long ll;
typedef unsigned long long ull;
//typedef __int128 bll;
typedef pair<ll ,ll > pll;
typedef pair<int ,int > pii;
typedef pair<int,pii> p3;
//priority_queue<int> q;//这是一个大根堆q
//priority_queue<int,vector<int>,greater<int> >q;//这是一个小根堆q
#define fi first
#define se second
//#define endl ''\n''
#define boost ios::sync_with_stdio(false);cin.tie(0)
#define rep(a, b, c) for(int a = (b); a <= (c); ++ a)
#define max3(a,b,c) max(max(a,b), c);
#define min3(a,b,c) min(min(a,b), c);
const ll oo = 1ll<<17;
const ll mos = 0x7FFFFFFF; //2147483647
const ll nmos = 0x80000000; //-2147483648
const int inf = 0x3f3f3f3f;
const ll inff = 0x3f3f3f3f3f3f3f3f; //18
const int mod = 1e9+7;
const double esp = 1e-8;
const double PI=acos(-1.0);
const double PHI=0.61803399; //黄金分割点
const double tPHI=0.38196601;
template<typename T>
inline T read(T&x){
x=0;int f=0;char ch=getchar();
while (ch<''0''||ch>''9'') f|=(ch==''-''),ch=getchar();
while (ch>=''0''&&ch<=''9'') x=x*10+ch-''0'',ch=getchar();
return x=f?-x:x;
}
inline void cmax(int &x,int y){if(x<y)x=y;}
inline void cmax(ll &x,ll y){if(x<y)x=y;}
inline void cmin(int &x,int y){if(x>y)x=y;}
inline void cmin(ll &x,ll y){if(x>y)x=y;}
/*-----------------------showtime----------------------*/
string str[10];
map<string ,int>mp;
vector<int>G[509];
int fa[509],du[509],dig[509];
int find(int x) {
if(fa[x] == x) return x;
return fa[x] = find(fa[x]);
}
int dfs(int s,int t){
int flag = 0;
for(int i=0; i<G[s].size(); i++){
int v = G[s][i];
if(v == t) flag = 1;
flag = (flag || dfs(v, t));
}
return flag;
}
int main(){
int n,m;
scanf("%d%d", &n, &m);
int tot = 0;
rep(i, 1, 508) fa[i] = i;
rep(i, 1, n) {
rep(j, 1, 5) cin>>str[j];
int u,v;
if(mp.count(str[1])) u = mp[str[1]];
else {
++tot; u = tot;
mp[str[1]] = tot;
}
if(mp.count(str[5])) v = mp[str[5]];
else {
++tot; v = tot;
mp[str[5]] = tot;
}
int fx = find(u), fy = find(v);
fa[fx]= fy;
G[u].pb(v);
}
for(int i=1; i<=m; i++){
rep(j, 1, 5) cin>>str[j];
if(mp.count(str[1]) == 0 || mp.count(str[5]) == 0) {
puts("Pants on Fire");
continue;
}
int u = mp[str[1]];
int v = mp[str[5]];
if(find(u) != find(v) ) puts("Pants on Fire");
else if(dfs(u, v)) puts("Fact");
else if(dfs(v, u))puts("Alternative Fact");
else puts("Pants on Fire");
}
return 0;
}E Perpetuum Mobile
spfa判正权环
代码：
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize(4)
#include<bits/stdc++.h>
using namespace std;
#define y1 y11
#define fi first
#define se second
#define pi acos(-1.0)
#define LL long long
//#define mp make_pair
#define pb push_back
#define ls rt<<1, l, m
#define rs rt<<1|1, m+1, r
#define ULL unsigned LL
#define pll pair<LL, LL>
#define pli pair<LL, int>
#define pii pair<int, int>
#define piii pair<pii, int>
#define pdd pair<double, double>
#define mem(a, b) memset(a, b, sizeof(a))
#define debug(x) cerr << #x << " = " << x << "\n";
#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
//head
const int N = 800 + 10;
double d[N];
struct edge {
int to;
double w;
};
vector<edge> g[N];
bool vis[N];
bool spfa(int u) {
vis[u] = true;
for (edge v : g[u]) {
if(d[u] + v.w < d[v.to]) {
d[v.to] = d[u] + v.w;
if(vis[v.to]) return true;
if(spfa(v.to)) return true;
}
}
vis[u] = false;
return false;
}
int main() {
int n, m, u, v;
double w;
scanf("%d %d", &n, &m);
for (int i = 1; i <= m; ++i) {
scanf("%d %d %lf", &u, &v, &w);
g[u].pb({v, -log(w)});
}
for (int i = 1; i <= n; ++i) d[i] = 0;
for (int i = 1; i <= n; ++i) if(spfa(i)) {
puts("inadmissible");
return 0;
}
puts("admissible");
return 0;
}F Plug It In
枚举三个插座的位置，拆点，然后二分图匹配
代码：
#include <algorithm>
#include <iterator>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <iomanip>
#include <bitset>
#include <cctype>
#include <cstdio>
#include <string>
#include <vector>
#include <stack>
#include <cmath>
#include <queue>
#include <list>
#include <map>
#include <set>
#include <cassert>
/*
⊂_ヽ
＼＼ Λ＿Λ 来了老弟
＼(''ㅅ'')
> ⌒ヽ
/ へ＼
/ / ＼＼
ﾚ ノ ヽ_つ
/ /
/ /|
( (ヽ
| |、＼
| 丿 ＼ ⌒)
| | ) /
''ノ ) Lﾉ
*/
using namespace std;
#define lson (l , mid , rt << 1)
#define rson (mid + 1 , r , rt << 1 | 1)
#define debug(x) cerr << #x << " = " << x << "\n";
#define pb push_back
#define pq priority_queue
typedef long long ll;
typedef unsigned long long ull;
//typedef __int128 bll;
typedef pair<ll ,ll > pll;
typedef pair<int ,int > pii;
typedef pair<int,pii> p3;
//priority_queue<int> q;//这是一个大根堆q
//priority_queue<int,vector<int>,greater<int> >q;//这是一个小根堆q
#define fi first
#define se second
//#define endl ''\n''
#define boost ios::sync_with_stdio(false);cin.tie(0)
#define rep(a, b, c) for(int a = (b); a <= (c); ++ a)
#define max3(a,b,c) max(max(a,b), c);
#define min3(a,b,c) min(min(a,b), c);
const ll oo = 1ll<<17;
const ll mos = 0x7FFFFFFF; //2147483647
const ll nmos = 0x80000000; //-2147483648
const int inf = 0x3f3f3f3f;
const ll inff = 0x3f3f3f3f3f3f3f3f; //18
const int mod = 1e9+7;
const double esp = 1e-8;
const double PI=acos(-1.0);
const double PHI=0.61803399; //黄金分割点
const double tPHI=0.38196601;
template<typename T>
inline T read(T&x){
x=0;int f=0;char ch=getchar();
while (ch<''0''||ch>''9'') f|=(ch==''-''),ch=getchar();
while (ch>=''0''&&ch<=''9'') x=x*10+ch-''0'',ch=getchar();
return x=f?-x:x;
}
inline void cmax(int &x,int y){if(x<y)x=y;}
inline void cmax(ll &x,ll y){if(x<y)x=y;}
inline void cmin(int &x,int y){if(x>y)x=y;}
inline void cmin(ll &x,ll y){if(x>y)x=y;}
/*-----------------------showtime----------------------*/
const int maxn = 1509;
int pt[maxn],vis[maxn];
struct node{
int cnt;
int id;
}a[maxn];
queue<int>que;
vector<int>mp[maxn];
int col = 0;
bool dfs(int u){
if(vis[u] == col) return false;
vis[u] = col;
for(int i=0; i<mp[u].size(); i++){
int v = mp[u][i];
if(pt[v] ==0 || dfs(pt[v])) {
pt[v] = u;
return true;
};
}
return false;
}
int in[maxn];
bool cmp(node a,node b){
return a.cnt < b.cnt;
}
int main(){
int n,m,k;
scanf("%d%d%d", &n, &m, &k);
rep(i, 1, m) a[i].id = i;
for(int i=1; i<=k; i++){
int u,v;
scanf("%d%d", &u, &v);
mp[v].pb(u);
a[v].cnt++;
}
sort(a+1, a+1+m, cmp);
int ans = 0;
for(int i=1; i<=m; i++) {
// memset(vis, 0, sizeof(vis));
col++;
if(dfs(a[i].id) == 0) que.push(a[i].id);
else ans++;
}
int mx = 0;
while(!que.empty()){
int u = que.front(); que.pop();
for(int i=0; i<mp[u].size(); i++)
{
int v = mp[u][i];
in[v]++;
mx = max(mx, in[v]);
}
}
mx = min(2, mx);
ans += mx;
printf("%d\n", ans);
return 0;
}G Water Testing
皮克定理
代码：
#include<bits/stdc++.h>
#define int long long
#define MAX(a,b,c) max(a,max(b,c))
#define MIN(a,b,c) min(a,min(b,c))
#define pb push_back
#define fi first
#define se second
typedef long long ll;
typedef long long LL;
typedef unsigned long long ull;
typedef unsigned long long uLL;
using namespace std;
const int maxn=1e6+10;
const int mod=1e9+7;
struct Point{int x;int y;}pa[maxn];
int Cross(Point A,Point B) { return A.x*B.y-A.y*B.x; } // 叉积
/*bool anglecmp(Point a, Point b)
{
if(a.y <= 0 && b.y > 0) return true;
if(a.y > 0 && b.y <= 0) return false;
if(!a.y && !b.y) return a.x < b.x;
return Cross(a,b) > 0;
}*/
int work(Point a,Point b)
{
return __gcd( abs(a.x-b.x),abs(b.y-a.y) )-1;
}
int32_t main()
{
int n; scanf("%lld",&n);
for(int i=1;i<=n;i++) scanf("%lld %lld",&pa[i].x,&pa[i].y);
//sort(pa+1,pa+1+n,anglecmp);
int ans=0;
for(int i=1;i<n;i++)
ans+=Cross(pa[i],pa[i+1]);
ans+=Cross(pa[n],pa[1]);
ans=abs(ans);
int x=n;
for(int i=1;i<n;i++)
x+=work(pa[i],pa[i+1]);
x+=work(pa[n],pa[1]);
int a=(ans-x+2)/2;
printf("%lld\n",a);
}H Ratatoskr
枚举根，求最长链，然后取最小
代码：
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize(4)
#include<bits/stdc++.h>
using namespace std;
#define y1 y11
#define fi first
#define se second
#define pi acos(-1.0)
#define LL long long
//#define mp make_pair
#define pb push_back
#define ls rt<<1, l, m
#define rs rt<<1|1, m+1, r
#define ULL unsigned LL
#define pll pair<LL, LL>
#define pli pair<LL, int>
#define pii pair<int, int>
#define piii pair<pii, int>
#define pdd pair<double, double>
#define mem(a, b) memset(a, b, sizeof(a))
#define debug(x) cerr << #x << " = " << x << "\n";
const int N = 85;
vector<int> g[N];
int dfs(int u, int o) {
int res = 1;
for (int v : g[u]) {
if(v != o) res = max(res, dfs(v, u)+1);
}
return res;
}
int main() {
int n, a, b, c, u, v;
scanf("%d", &n);
scanf("%d %d %d", &a, &b, &c);
for (int i = 1; i < n; ++i) scanf("%d %d", &u, &v), g[u].pb(v), g[v].pb(u);
int ans = n;
for (int i = 1; i <= n; ++i) {
if(i == b || i == c) ans =min(ans, dfs(i, i)-1);
else ans = min(dfs(i, i), ans);
}
printf("%d\n", ans);
return 0;
}I Uberwatch
dp
代码：
#include <algorithm>
#include <iterator>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <iomanip>
#include <bitset>
#include <cctype>
#include <cstdio>
#include <string>
#include <vector>
#include <stack>
#include <cmath>
#include <queue>
#include <list>
#include <map>
#include <set>
#include <cassert>
/*
⊂_ヽ
＼＼ Λ＿Λ 来了老弟
＼(''ㅅ'')
> ⌒ヽ
/ へ＼
/ / ＼＼
ﾚ ノ ヽ_つ
/ /
/ /|
( (ヽ
| |、＼
| 丿 ＼ ⌒)
| | ) /
''ノ ) Lﾉ
*/
using namespace std;
#define lson (l , mid , rt << 1)
#define rson (mid + 1 , r , rt << 1 | 1)
#define debug(x) cerr << #x << " = " << x << "\n";
#define pb push_back
#define pq priority_queue
typedef long long ll;
typedef unsigned long long ull;
//typedef __int128 bll;
typedef pair<ll ,ll > pll;
typedef pair<int ,int > pii;
typedef pair<int,pii> p3;
//priority_queue<int> q;//这是一个大根堆q
//priority_queue<int,vector<int>,greater<int> >q;//这是一个小根堆q
#define fi first
#define se second
//#define endl ''\n''
#define boost ios::sync_with_stdio(false);cin.tie(0)
#define rep(a, b, c) for(int a = (b); a <= (c); ++ a)
#define max3(a,b,c) max(max(a,b), c);
#define min3(a,b,c) min(min(a,b), c);
const ll oo = 1ll<<17;
const ll mos = 0x7FFFFFFF; //2147483647
const ll nmos = 0x80000000; //-2147483648
const int inf = 0x3f3f3f3f;
const ll inff = 0x3f3f3f3f3f3f3f3f; //18
const int mod = 1e9+7;
const double esp = 1e-8;
const double PI=acos(-1.0);
const double PHI=0.61803399; //黄金分割点
const double tPHI=0.38196601;
template<typename T>
inline T read(T&x){
x=0;int f=0;char ch=getchar();
while (ch<''0''||ch>''9'') f|=(ch==''-''),ch=getchar();
while (ch>=''0''&&ch<=''9'') x=x*10+ch-''0'',ch=getchar();
return x=f?-x:x;
}
inline void cmax(int &x,int y){if(x<y)x=y;}
inline void cmax(ll &x,ll y){if(x<y)x=y;}
inline void cmin(int &x,int y){if(x>y)x=y;}
inline void cmin(ll &x,ll y){if(x>y)x=y;}
/*-----------------------showtime----------------------*/
const int maxn = 3e5+9;
int a[maxn],dp[maxn],res[maxn];
int main(){
int n,m;
scanf("%d%d", &n, &m);
rep(i, 1, n) scanf("%d", &a[i]);
rep(i, m+1, n) {
dp[i] = max(dp[i],res[i-m] + a[i]);
res[i] = max(res[i-1], dp[i]);
}
printf("%d\n", res[n]);
return 0;
}J Word Clock
旅行商问题变形，状压dp实现
代码:
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize(4)
#include<bits/stdc++.h>
using namespace std;
#define y1 y11
#define fi first
#define se second
#define pi acos(-1.0)
#define LL long long
//#define mp make_pair
#define pb push_back
#define ls rt<<1, l, m
#define rs rt<<1|1, m+1, r
#define ULL unsigned LL
#define pll pair<LL, LL>
#define pli pair<LL, int>
#define pii pair<int, int>
#define piii pair<pii, int>
#define pdd pair<double, double>
#define mem(a, b) memset(a, b, sizeof(a))
#define debug(x) cerr << #x << " = " << x << "\n";
#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
const int N = 19;
const int INF = 0x3f3f3f3f;
int h, w, n;
string t[N], s[N];
int d[N][N], up;
pii dp[N][1<<N];
int pre[N][1<<N];
pii dfs(int u, int st) {
if(~dp[u][st].fi) return dp[u][st];
pii res = {INF, INF};
for (int i = 0; i < n; ++i) {
if(i == u) continue;
if(st & (1<<i)) {
pii p = dfs(i, st^(1<<u));
p.se += d[i][u];
if(p.se > w) p.fi++, p.se = s[u].size();
if(p < res) {
res = p;
pre[u][st] = i;
}
}
}
if(res.fi == INF) res.fi = 0, res.se = s[u].size();
return dp[u][st] = res;
}
int main() {
fio;
cin >> h >> w >> n;
int tot = 0;
for (int i = 0; i < n; ++i) cin >> t[i];
for (int i = 0; i < n; ++i) {
bool f = true;
if(t[i].size() > w) return 0*puts("impossible");
for (int j = 0; j < n; ++j) {
if(i == j) continue;
if(t[j].find(t[i]) == string::npos) continue;
f = false;
}
if(f) s[tot++] = t[i];
}
n = tot;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
if(i == j) continue;
int mn = min(s[i].size(), s[j].size());
d[i][j] = s[j].size();
for (int k = 1; k <= mn; ++k) {
if(s[i].substr(s[i].size()-k, k) == s[j].substr(0, k)) d[i][j] = s[j].size() - k; ///!!!!!!!!!
}
}
}
up = 1<<n;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < up; ++j)
dp[i][j] = {-1, -1}, pre[i][j] = -1;
}
for (int i = 0; i < n; ++i) {
pii p = dfs(i, up-1);
if(p.fi < h) {
vector<string> res (h, string(w, ''X''));
vector<int> p;
int now = i, st = up-1;
while(~now) {
p.pb(now);
now = pre[now][st];
st ^= 1<<p.back();
}
reverse(p.begin(), p.end());
pii pos = {0, 0};
for (int i = 0; i < p.size(); ++i) {
int x = p[i];
if(i == 0) {
for (int j = 0; j < s[x].size(); ++j) res[pos.fi][pos.se+j] = s[x][j];
pos.se += s[x].size();
}
else {
int u = p[i-1];
if(pos.se + d[u][x] > w) {
pos.fi++;
pos.se = 0;
for (int j = 0; j < s[x].size(); ++j) res[pos.fi][pos.se+j] = s[x][j];
pos.se = s[x].size();
}
else {
int sz = s[x].size();
for (int j = 0; j < d[u][x]; ++j) res[pos.fi][pos.se+j] = s[x][sz-d[u][x]+j];
pos.se += d[u][x];
}
}
}
for (int i = 0; i < h; ++i) cout << res[i] << endl;
return 0;
}
}
return 0*puts("impossible");
}K You Are Fired
排序
代码：
#include <algorithm>
#include <iterator>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <iomanip>
#include <bitset>
#include <cctype>
#include <cstdio>
#include <string>
#include <vector>
#include <stack>
#include <cmath>
#include <queue>
#include <list>
#include <map>
#include <set>
#include <cassert>
/*
⊂_ヽ
＼＼ Λ＿Λ 来了老弟
＼(''ㅅ'')
> ⌒ヽ
/ へ＼
/ / ＼＼
ﾚ ノ ヽ_つ
/ /
/ /|
( (ヽ
| |、＼
| 丿 ＼ ⌒)
| | ) /
''ノ ) Lﾉ
*/
using namespace std;
#define lson (l , mid , rt << 1)
#define rson (mid + 1 , r , rt << 1 | 1)
#define debug(x) cerr << #x << " = " << x << "\n";
#define pb push_back
#define pq priority_queue
typedef long long ll;
typedef unsigned long long ull;
//typedef __int128 bll;
typedef pair<ll ,ll > pll;
typedef pair<int ,int > pii;
typedef pair<int,pii> p3;
//priority_queue<int> q;//这是一个大根堆q
//priority_queue<int,vector<int>,greater<int> >q;//这是一个小根堆q
#define fi first
#define se second
//#define endl ''\n''
#define boost ios::sync_with_stdio(false);cin.tie(0)
#define rep(a, b, c) for(int a = (b); a <= (c); ++ a)
#define max3(a,b,c) max(max(a,b), c);
#define min3(a,b,c) min(min(a,b), c);
const ll oo = 1ll<<17;
const ll mos = 0x7FFFFFFF; //2147483647
const ll nmos = 0x80000000; //-2147483648
const int inf = 0x3f3f3f3f;
const ll inff = 0x3f3f3f3f3f3f3f3f; //18
const int mod = 1e9+7;
const double esp = 1e-8;
const double PI=acos(-1.0);
const double PHI=0.61803399; //黄金分割点
const double tPHI=0.38196601;
template<typename T>
inline T read(T&x){
x=0;int f=0;char ch=getchar();
while (ch<''0''||ch>''9'') f|=(ch==''-''),ch=getchar();
while (ch>=''0''&&ch<=''9'') x=x*10+ch-''0'',ch=getchar();
return x=f?-x:x;
}
inline void cmax(int &x,int y){if(x<y)x=y;}
inline void cmax(ll &x,ll y){if(x<y)x=y;}
inline void cmin(int &x,int y){if(x>y)x=y;}
inline void cmin(ll &x,ll y){if(x>y)x=y;}
/*-----------------------showtime----------------------*/
const int maxn = 1e4+9;
struct node{
string name;
ll x;
}a[maxn];
bool cmp(node a, node b){
return a.x > b.x;
}
int main(){
ll n, d, k;
cin>>n>>d>>k;
rep(i,1, n)
{
cin>>a[i].name>>a[i].x;
}
sort(a+1,a+1+n,cmp);
ll sum = 0;
rep(i,1, k) sum += a[i].x;
if(sum < d) puts("impossible");
else {
printf("%d\n", k);
rep(i, 1, k) {
cout<<a[i].name<<", YOU ARE FIRED!"<<endl;
}
}
return 0;
}
2017-2018 ACM-ICPC German Collegiate Programming Contest (GCPC 2017) Solution
A. Drawing Borders
Unsolved.
B. Buildings
Unsolved.
C. Joyride
Upsolved.
题意：
在游乐园中，有 n 个游玩设施，有些设施之间有道路，给出每个设施需要花费的时间和价格，以及经过每条道路的时间，求从设施 1 出发恰好回到设施 1 恰好花费时间 x 的最小花费。
思路：
$dist [i][j] 表示 第 i 个时刻 到第 j 个点的最小花费 从 < t [1], 1> -> <x, 1>$
跑最短路即可
1 #include <bits/stdc++.h>
2 using namespace std;
3
4 #define N 3010
5 #define ll long long
6 #define INF 0x3f3f3f3f3f3f3f3f
7 int X, n, m, T, t[N], p[N];
8 vector <int> G[N];
9
10 struct node
11 {
12 int x, to; ll w;
13 node () {}
14 node (int x, int to, ll w) : x(x), to(to), w(w) {}
15 bool operator < (const node &r) const { return w > r.w; }
16 };
17
18 bool used[N][N];
19 ll dist[N][N];
20 void Dijkstra()
21 {
22 for (int i = 1; i <= X; ++i) for (int j = 1; j <= n; ++j) dist[i][j] = INF, used[i][j] = 0;
23 priority_queue <node> q; q.emplace(t[1], 1, 0); dist[t[1]][1] = p[1];
24 while (!q.empty())
25 {
26 int x = q.top().x, u = q.top().to; q.pop();
27 if (x > X) continue;
28 if (used[x][u]) continue;
29 used[x][u] = 1;
30 if (!used[x + t[u]][u] && dist[x + t[u]][u] > dist[x][u] + p[u])
31 {
32 dist[x + t[u]][u] = dist[x][u] + p[u];
33 q.emplace(x + t[u], u, dist[x + t[u]][u]);
34 }
35 for (auto v : G[u]) if (!used[x + t[v] + T][v] && dist[x + t[v] + T][v] > dist[x][u] + p[v])
36 {
37 dist[x + t[v] + T][v] = dist[x][u] + p[v];
38 q.emplace(x + t[v] + T, v, dist[x + t[v] + T][v]);
39 }
40 }
41 }
42
43 int main()
44 {
45 while (scanf("%d", &X) != EOF)
46 {
47 scanf("%d%d%d", &n, &m, &T);
48 for (int i = 1, u, v; i <= m; ++i)
49 {
50 scanf("%d%d", &u, &v);
51 G[u].push_back(v);
52 G[v].push_back(u);
53 }
54 for (int i = 1; i <= n; ++i) scanf("%d%d", t + i, p + i);
55 Dijkstra();
56 if (dist[X][1] == INF) puts("It is a trap.");
57 else printf("%lld\n", dist[X][1]);
58 }
59 return 0;
60 }
D. Pants On Fire
Solved.
题意：
给出一些关系，再给出一些关系的询问，对于询问给出三种结果。
思路：
Floyd 求闭包，但是我还是想知道为什么拓扑排序不行，难道是题意读错，它不一定是个 DAG?
1 #include <bits/stdc++.h>
2 using namespace std;
3
4 #define N 410
5 int n, m;
6 map <string, int> mp; int cnt;
7 char a[N], b[N];
8 int G[N][N];
9
10 int getid(char *s)
11 {
12 if (mp.find(s) == mp.end()) mp[s] = ++cnt;
13 return mp[s];
14 }
15
16 void Floyd()
17 {
18 for (int k = 1; k <= cnt; ++k)
19 {
20 for (int i = 1; i <= cnt; ++i)
21 {
22 for (int j = 1; j <= cnt; ++j)
23 {
24 if (G[i][k] & G[k][j])
25 G[i][j] = 1;
26 }
27 }
28 }
29 }
30
31 void init()
32 {
33 memset(G, 0, sizeof G);
34 mp.clear(); cnt = 0;
35 }
36
37 int main()
38 {
39 while (scanf("%d%d", &n, &m) != EOF)
40 {
41 init();
42 for (int i = 1, u, v; i <= n; ++i)
43 {
44 scanf("%s are worse than %s", a, b);
45 u = getid(a), v = getid(b);
46 G[u][v] = 1;
47 }
48 Floyd();
49 //for (auto it : mp) cout << it.first << " " << rt[it.second] << " " << deep[it.second] << endl;
50 for (int i = 1, u, v; i <= m; ++i)
51 {
52 scanf("%s are worse than %s", a, b);
53 u = getid(a), v = getid(b);
54 if (G[u][v] == 1) puts("Fact");
55 else if (G[v][u] == 1) puts("Alternative Fact");
56 else puts("Pants on Fire");
57 }
58 }
59 return 0;
60 }
E. Perpetuum Mobile
Upsolved.
题意：
有 n 个转换器，m 个转换关系，转换关系是有向边
求从哪个点出发回到起点后经过的转换大于原来的值
思路：
枚举起点跑最长路，乘法可以取个 $log$, 当然也可以再取个负跑最短路也可以
1 #include <bits/stdc++.h>
2 using namespace std;
3
4 #define N 10010
5 #define INF 0x3f3f3f3f
6 #define pid pair <int, double>
7 int n, m;
8 vector <pid> G[N];
9
10 struct node
11 {
12 int to; double w;
13 node () {}
14 node (int to, double w) : to(to), w(w) {}
15 bool operator < (const node &r) const { return w < r.w; }
16 };
17
18 double dist[N]; bool used[N];
19 bool Dijkstra(int st)
20 {
21 for (int i = 1; i <= n; ++i) dist[i] = 0.0, used[i] = false;
22 priority_queue <node> q; q.emplace(st, 0);
23 while (!q.empty())
24 {
25 int u = q.top().to; q.pop();
26 if (used[u] && u == st && dist[u] > 0) return false;
27 if (used[u]) continue;
28 used[u] = 1;
29 for (auto it : G[u]) if (dist[it.first] < dist[u] + log(it.second))
30 {
31 dist[it.first] = dist[u] + log(it.second);
32 q.emplace(it.first, dist[it.first]);
33 }
34 }
35 return true;
36 }
37
38 bool solve()
39 {
40 for (int i = 1; i <= n; ++i) if (Dijkstra(i) == false)
41 return false;
42 return true;
43 }
44
45 int main()
46 {
47 while (scanf("%d%d", &n, &m) != EOF)
48 {
49 for (int i = 1; i <= n; ++i) G[i].clear();
50 double w;
51 for (int i = 1, u, v; i <= m; ++i)
52 {
53 scanf("%d%d%lf", &u, &v, &w);
54 G[u].emplace_back(v, w);
55 }
56 if (solve() == false) printf("in");
57 puts("admissible");
58 }
59 return 0;
60 }
F. Plug It In
Unsolved.
题意：
给出一个匹配关系，可以设置一个人和三个人匹配，求最大匹配数。
思路：
先求最大匹配，再枚举每个插座，找增广路，枚举点的时候都要复制原图备份一下
1 #include <bits/stdc++.h>
2 using namespace std;
3
4 #define N 1510
5 int n, m, k;
6 vector <int> G[N];
7 int linker[N], vis[N], tmp[N];
8
9 bool DFS(int u)
10 {
11 for (auto v : G[u]) if (!vis[v])
12 {
13 vis[v] = 1;
14 if (linker[v] == -1 || DFS(linker[v]))
15 {
16 linker[v] = u;
17 return true;
18 }
19 }
20 return false;
21 }
22
23 int main()
24 {
25 while (scanf("%d%d%d", &n, &m, &k) != EOF)
26 {
27 for (int i = 1; i <= n; ++i) G[i].clear();
28 for (int i = 1, u, v; i <= k; ++i)
29 {
30 scanf("%d%d", &u, &v);
31 G[u].push_back(v);
32 }
33 memset(linker, -1, sizeof linker);
34 int res = 0, ans = 0;
35 for (int i = 1; i <= n; ++i)
36 {
37 memset(vis, 0, sizeof vis);
38 if (DFS(i)) ++res;
39 }
40 memcpy(tmp, linker, sizeof linker);
41 for (int i = 1; i <= n; ++i)
42 {
43 int cnt = 0;
44 for (int j = 1; j <= 2; ++j)
45 {
46 memset(vis, 0, sizeof vis);
47 if (DFS(i)) ++cnt;
48 }
49 ans = max(ans, cnt);
50 memcpy(linker, tmp, sizeof tmp);
51 }
52 printf("%d\n", res + ans);
53 }
54 return 0;
55 }
G. Water Testing
Upsolved.
题意：求一个多边形内部整点个数。
思路：
皮克定理：$S = a + \frac {b}{2} - 1 S 表示多边形面积，\frac {b}{2} 表示 多边形边上的整点数 a 表示多边形内部整点数 $
因为点是按顺序给出，有求面积公式 $S = \frac {1}{2} \sum_{i = 0}^{i = n}|\vec {P_i} x \vec {P_i - 1}|$
再考虑 线段上的整点个数为
$ 令 a = abs (stx - edx), b = abs (sty - edy)，整点个数为 gcd (a, b) + 1$
考虑证明：
根据直线两点式有：
$y - y_1 = \frac{y_2 - y_1}{x_2 - x_1} \cdot (x - x _1)$
移项得
$y = \frac{y_2 - y_1}{x_2 - x_1} \cdot (x - x_1) + y_1$
即考虑 有多少个 $x 使得 (x - x_1) \equiv 0 \pmod {x_2 - x_1}$
由于 $x 在 [x1, x2] 范围内 那么 (x - x_1) 的范围即 [0, x2 - x1]$
$ 考虑 \frac {y_2 - y_1}{x_2 - x_1} 可以跟他们的 gcd 约分 $
$\frac{x_2 - x_1}{ \frac {x_2 - x_1}{gcd((y_2 - y_1), (x_2 - x_1))}} = gcd((y_2 - y_1), (x_2 - x_1))$
1 #include <bits/stdc++.h>
2 using namespace std;
3
4 #define N 100010
5 #define ll long long
6 int n;
7 ll x[N], y[N];
8
9 ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a;}
10
11 int main()
12 {
13 while (scanf("%d", &n) != EOF)
14 {
15 for (int i = 1; i <= n; ++i)
16 scanf("%lld%lld", x + i, y + i);
17 x[0] = x[n]; y[0] = y[n];
18 ll s = 0, b = 0;
19 for (int i = 1; i <= n; ++i)
20 {
21 s += x[i - 1] * y[i] - x[i] * y[i - 1];
22 ll A = abs(x[i] - x[i - 1]);
23 ll B = abs(y[i] - y[i - 1]);
24 b += gcd(A, B);
25 }
26 s = abs(s);
27 printf("%lld\n", (s - b + 2) >> 1);
28 }
29 return 0;
30 }
H. Ratatoskr
Unsolved.
I. Uberwatch
Water.
1 #include <bits/stdc++.h>
2 using namespace std;
3
4 #define N 300010
5 int n, m, x[N], Max[15];
6
7 int main()
8 {
9 while (scanf("%d%d", &n, &m) != EOF)
10 {
11 memset(Max, 0, sizeof Max);
12 for (int i = 1; i <= n; ++i) scanf("%d", x + i);
13 for (int i = m + 1, res; i <= n; ++i)
14 {
15 res = x[i] + Max[m];
16 for (int j = m; j >= 1; --j) Max[j] = max(Max[j], Max[j - 1]);
17 Max[1] = max(Max[1], res);
18 }
19 printf("%d\n", *max_element(Max + 1, Max + 1 + m));
20 }
21 return 0;
22 }
J. Word Clock
Unsolved.
K. You Are Fired
Water.
1 #include <bits/stdc++.h>
2 using namespace std;
3
4 #define N 10010
5 int n, k, d;
6 struct node
7 {
8 char s[10]; int c;
9 void scan()
10 {
11 scanf("%s%d", s, &c);
12 }
13 bool operator < (const node &r) const {return c > r.c;}
14 }emp[N];
15
16 int main()
17 {
18 while (scanf("%d%d%d", &n, &d, &k) != EOF)
19 {
20 for (int i = 1; i <= n; ++i) emp[i].scan();
21 sort(emp + 1, emp + 1 + n);
22 int tot = 0;
23 for (int i = 1; i <= k; ++i) tot += emp[i].c;
24 if (tot < d) puts("impossible");
25 else
26 {
27 printf("%d\n", k);
28 for (int i = 1; i <= k; ++i) printf("%s, YOU ARE FIRED!\n", emp[i].s);
29 }
30 }
31 return 0;
32 }
2017-2018 ACM-ICPC Nordic Collegiate Programming Contest (NCPC 2017) D bfs 思维 E bfs I Floyd 找最小环...
2017-2018 ACM-ICPC Nordic Collegiate Programming Contest (NCPC 2017)
D
题意：有 n 个人，每个人有 k 个特征，每个特征值为 0 或 1。 定义两人的相似度为：k 个特征值中相同的个数。 要你另外找一个人，这个人和其他人相似度的最大值要尽可能小。
tags：bfs，思维
找一个人与其他人相似度的最大值尽可能小，也就是这个人与其他人 不相似度的最小值要尽可能大。
那我们可把这 n 个人当成 n 个点，总共有 (1<<k) 个点。我们以这 n 个点为起点 bfs，每走一步改变一个特征值，即 不相似度 +1 。最后找 不相似度最大的就是了。
// D
#include<bits/stdc++.h>
using namespace std;
#pragma comment(linker, "/STACK:102400000,102400000")
#define rep(i,a,b) for (int i=a; i<=b; ++i)
#define per(i,b,a) for (int i=b; i>=a; --i)
#define mes(a,b) memset(a,b,sizeof(a))
#define INF 0x3f3f3f3f
#define MP make_pair
#define PB push_back
#define fi first
#define se second
typedef long long ll;
const int N = 2000005;
int n, k, dis[N];
char str[N];
queue< int > q;
void bfs()
{
int u, to;
while(!q.empty())
{
u = q.front(); q.pop();
rep(j,1,k)
{
to = u^(1<<(j-1));
if(dis[to]==-1) {
dis[to] = dis[u]+1;
q.push(to);
}
}
}
}
int main()
{
scanf("%d%d", &n, &k);
mes(dis, -1);
rep(i,1,n)
{
scanf("%s", str+1);
int tmp = 0;
rep(j,1,k)
if(str[j]==''1'') tmp+=1<<(j-1);
dis[tmp]=0; q.push(tmp);
}
bfs();
int ans1, ans2=0;
rep(i,0,(1<<k)-1)
if(dis[i]>=ans2) ans1=i, ans2=dis[i];
rep(j,1,k)
if((ans1>>(j-1))&1) putchar(''1'');
else putchar(''0'');
return 0;
}
E
题意：n*m 的地方，每个地方给出高度，所有 n*m 的地方有海拔为 0 的积水。 现在给出一个点作为排水口，每个地方的水可以往周围八个方向，且比它低的地方流。问最后会流走多少水。
tags：bfs 跑一遍，同时要记录每个点可以下降到的最低点，且优生走更低的点。
// E
#include<bits/stdc++.h>
using namespace std;
#pragma comment(linker, "/STACK:102400000,102400000")
#define rep(i,a,b) for (int i=a; i<=b; ++i)
#define per(i,b,a) for (int i=b; i>=a; --i)
#define mes(a,b) memset(a,b,sizeof(a))
#define INF 0x3f3f3f3f
#define MP make_pair
#define PB push_back
#define fi first
#define se second
typedef long long ll;
const int N = 505;
int n, m, a[N][N], ans[N][N];
struct Node {
int x, y, h;
bool friend operator<(Node a, Node b) {
return a.h > b.h;
}
};
int dirx[8] = {1, -1, 0, 0, 1, 1, -1, -1};
int diry[8] = {0, 0, 1, -1, 1, -1, -1, 1};
priority_queue< Node > q;
bool check(int x, int y) {
return x>0 && x<=n && y>0 && y<=m;
}
void bfs(int x, int y, int h)
{
Node u;
q.push((Node){ x,y,h });
int tx, ty;
while(!q.empty())
{
u = q.top(); q.pop();
x=u.x, y=u.y, h=u.h;
if(ans[x][y]<h) continue;
rep(i,0,7)
{
tx=x+dirx[i], ty=y+diry[i];
if(check(tx,ty) && max(a[tx][ty],h)<0 && ans[tx][ty]>max(a[tx][ty],h))
{
ans[tx][ty] = max(h, a[tx][ty]);
q.push((Node){ tx,ty,ans[tx][ty] });
}
}
}
}
int main()
{
scanf("%d%d", &n, &m);
rep(i,1,n) rep(j,1,m)
scanf("%d", &a[i][j]);
int tx, ty;
scanf("%d%d", &tx, &ty);
ans[tx][ty]=min(0, a[tx][ty]);
bfs(tx, ty, a[tx][ty]);
ll ans1 = 0;
rep(i,1,n) rep(j,1,m)
if(ans[i][j]<0)
ans1 += -ans[i][j];
printf("%lld\n", ans1);
return 0;
}
I
题意： n 个文件，每个文件可以调用多个其它的文件，问最小的循环调用，且输出路径。 也就是在 DAG 图中找一个最小环。
tags：套板子 -_-
Floyd 有向图找最小环
// Floyd 找有向图最小环
const int N = 505;
int G[N][N], n ,m, dist[N][N], past[N][N];
int mincircle, path[N], cnt;
void Init_Floyd()
{
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++)
G[i][j] = INF;
}
void Floyd()
{
mincircle = INF;
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++)
dist[i][j] = G[i][j], past[i][j] = i;
for(int k = 1; k <= n; k++) //每个点都成为一次中间点，但和bellman-ford不一样
{
for(int i = 1; i <= n; i++) //判断是不是最小环
for(int j = 1; j <= n; j++)
{
if(i == j) continue;
if(dist[i][j]!=INF && G[j][k]!=INF && G[k][i]!=INF && mincircle>dist[i][j]+G[j][k]+G[k][i])
{
mincircle = dist[i][j]+G[j][k]+G[k][i];
cnt = 0;
int p=j;
while(p!=i) //逆向寻找前驱结点直到找到最前面的i,i->…->j
{
path[cnt++]=p;
p=past[i][p];
}
path[cnt++]=i;
path[cnt++]=k;
}
}
for(int i = 1; i <= n; i++) // 这里就是 Floyd算法
for(int j = 1; j <= n; j++)
{
if(i == k || j == k) continue;
if(dist[i][k]!=INF && dist[k][j]!=INF && dist[i][j]>dist[i][k]+dist[k][j])
{
dist[i][j] = dist[i][k]+dist[k][j];
past[i][j] = past[k][j];
}
}
}
}
void print_path()
{
if(mincircle==INF || mincircle<0)
puts("-1");
else {
for(int i=cnt-1; i>=0; --i)
printf("%d ", path[i]);
puts("");
}
}
// I
#include<bits/stdc++.h>
using namespace std;
#pragma comment(linker, "/STACK:102400000,102400000")
#define rep(i,a,b) for (int i=a; i<=b; ++i)
#define per(i,b,a) for (int i=b; i>=a; --i)
#define mes(a,b) memset(a,b,sizeof(a))
#define INF 0x3f3f3f3f
#define MP make_pair
#define PB push_back
#define fi first
#define se second
typedef long long ll;
const int N = 505;
int grap[N][N] , n , m;
int dist[N][N];
int past[N][N];
int mincircle;
int path[N] , k1 ;
void Init_Floyd()
{
int i , j;
for(i = 1; i <= n; i++)
for(j = 1; j <= n; j++)
grap[i][j] = INF;
}
void Floyd()
{
mincircle = INF;
int i , j;
for(i = 1; i <= n; i++)
for(j = 1; j <= n; j++)
{
dist[i][j] = grap[i][j];
past[i][j] = i;
}
for(int k = 1; k <= n; k++) //每个点都成为一次中间点 ， 和bellman-ford不一样
{
for(i = 1; i <= n; i++) //判断是不是最小环
for(j = 1; j <= n; j++)
{
//if(i == j) continue;
if(dist[i][j]!=INF && grap[j][k]!=INF && grap[k][i]!=INF && mincircle>dist[i][j]+grap[j][k]+grap[k][i])
{
mincircle = dist[i][j]+grap[j][k]+grap[k][i];
k1 = 0;
int p=j;
while(p!=i) //逆向寻找前驱结点直到找到最前面的i,i->…->j
{
path[k1++]=p;
p=past[i][p];//fa[i][j]保存的不是k,而是fa[k][j].
}
path[k1++]=i;
path[k1++]=k;
}
}
for(i = 1; i <= n; i++) //Floyd算法
for(j = 1; j <= n; j++)
{
//if(i == k || j == k) continue;
if(dist[i][k]!=INF && dist[k][j]!=INF && dist[i][j]>dist[i][k]+dist[k][j])
{
dist[i][j] = dist[i][k]+dist[k][j];
past[i][j] = past[k][j];
}
}
}
}
string str;
char si[N];
map<string , int > mp;
map<int , string > mp2;
int main()
{
scanf("%d", &n);
Init_Floyd();
rep(i,1,n) {
scanf("%s", si); str = si;
mp[str]=i, mp2[i]=str;
}
int k, u, len, to;
bool flag;
rep(i,1,n)
{
scanf("%s%d", si, &k); str = si;
u = mp[str];
rep(j,1,k)
{
scanf("%s", si);
while(~scanf("%s", si))
{
flag = false;
len = strlen(si);
if(si[len-1]=='','') {
flag=true;
si[len-1]=''\0'', --len;
}
str = si;
to = mp[str];
if(grap[u][to]>1)
grap[u][to]=1;
if(!flag) break;
}
}
}
rep(i,1,n) if(grap[i][i]<INF) {
cout<<mp2[i]<<endl;
return 0;
}
rep(i,1,n) rep(j,1,n)
{
if(i!=j && grap[i][j]==1 && grap[j][i]==1) {
cout<<mp2[i]<<" "<<mp2[j]<<endl;
return 0;
}
}
Floyd();
if(mincircle==INF || mincircle<0)
puts("SHIP IT");
else {
for(int i=k1-1; i>=0; --i)
cout<<mp2[path[i]]<<" ";
puts("");
}
return 0;
}
K
题意：有三种人，要过河，三种人分别有 b, n, e 个，每种人的系数是 sb,sn,se，有 (b+n+e)/2 条船，第 i 条船有速度 ci。每条船上坐两个人 x, y ，这条船的速度就是 ci*(sx+sy)。要你分配人和船，使得速度最小的船的速度要尽可能大。
tags：二分答案，然后 O (n) 贪心 check。
// k
#include<bits/stdc++.h>
using namespace std;
#pragma comment(linker, "/STACK:102400000,102400000")
#define rep(i,a,b) for (int i=a; i<=b; ++i)
#define per(i,b,a) for (int i=b; i>=a; --i)
#define mes(a,b) memset(a,b,sizeof(a))
#define INF 0x3f3f3f3f
#define MP make_pair
#define PB push_back
#define fi first
#define se second
typedef long long ll;
const int N = 200005;
int n, m, a[5], b[5], a2[5], c[N];
int cnt;
pair<int , pair<int, int > > p[10];
bool check(int x)
{
rep(i,1,3) a2[i]=a[i];
rep(i,1,m)
{
bool flag=false;
rep(j,1,cnt)
{
int t1=p[j].se.fi, t2=p[j].se.se;
if(t1!=t2 && (a2[t1]<1 || a2[t2]<1)) continue;
if(t1==t2 && a2[t1]<2) continue;
if(c[i]*p[j].fi >= x)
{
--a2[t1], --a2[t2];
flag=true; break;
}
}
if(!flag) return false;
}
return true;
}
int main()
{
rep(i,1,3) scanf("%d", &a[i]), m+=a[i];
m /= 2;
rep(i,1,3) scanf("%d", &b[i]);
rep(i,1,m) scanf("%d", &c[i]);
sort(c+1, c+1+m);
rep(i,1,3) rep(j,i,3)
p[++cnt]=MP(b[i]+b[j], MP(i,j));
sort(p+1, p+1+cnt);
int l=c[1]*(b[1]+b[1]), r=c[m]*(b[3]+b[3]), mid, ans;
while(l<=r)
{
mid = l+r>>1;
if(check(mid)) ans=mid, l=mid+1;
else r=mid-1;
}
printf("%d\n", ans);
return 0;
}
今天的关于2017 Android 和 iOS 频频被曝 Bug，它们都怎么了？和2017安卓的分享已经结束，谢谢您的关注，如果想了解更多关于(寒假开黑gym)2017-2018 ACM-ICPC German Collegiate Programming Contest (GCPC 2017)、2017-2018 ACM-ICPC German Collegiate Programming Contest (GCPC 2017)、2017-2018 ACM-ICPC German Collegiate Programming Contest (GCPC 2017) Solution、2017-2018 ACM-ICPC Nordic Collegiate Programming Contest (NCPC 2017) D bfs 思维 E bfs I Floyd 找最小环...的相关知识，请在本站进行查询。
本文标签：
![[转帖]Ubuntu 安装 Wine方法（ubuntu如何安装wine）](https://www.gvkun.com/zb_users/cache/thumbs/4c83df0e2303284d68480d1b1378581d-180-120-1.jpg)
