咕咕咕了好久
比赛地址
[A] Drawing Borders
题意
给出平面上的一些整点,这些点有三种不同的颜色.
现在要求在平面上画出两个多边形,使得某两种颜色的点恰好在这两个多边形中,要求两个多边形不能相交,不能有第三种颜色的点在多边形中.
题解
容易证明这样的多边形一定是存在的.
首先在所有点的右下角点一个点,然后向右一格格拉出一条直线,当发现在x=p的直线上有一个颜色标号为1的点的时候,就向上拐,走到和这个点差不多的高度,用一个小矩形把这个点包住,然后再拐下来.
对于另一种颜色的点也可以这么操作,只不过是从上面很远的地方开始画.可以证明,这样构造出的多边形点数小于10n,符合题意.
代码
#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
#include<map>
#include<queue>
#define l(x) (x<<1)
#define r(x) ((x<<1)|1)
#define IL inline
#define reg register
#define LL long long
#define N 110
#define INF 0x3f3f3f3f
using namespace std;
int n,i,p,q,cnt,sum,x;
queue <int> Q,P;
map <int,int> M;
struct Data{
int x,y,id;
}a[N];
struct Point{
double x,y;
}b[N*40],c[N*40];
IL int Abs(int x){return (x<0)?-x:x;}
IL void Swap(int &a,int &b){a^=b^=a^=b;}
IL int Min(int a,int b){return (a<b)?a:b;}
IL int Max(int a,int b){return (a>b)?a:b;}
IL int read(){
int p=0,f=1; char c=getchar();
while (c<48||c>57) {if (c=='-') f=-1; c=getchar();}
while (c>=48&&c<=57) p=(p<<1)+(p<<3)+c-48,c=getchar();
return p*f;
}
IL bool cmp(Data a,Data b){return (a.x==b.x)?a.y>b.y:a.x<b.x;}
int main(){
#ifdef __Marvolo
freopen("zht.in","r",stdin);
freopen("zht.out","w",stdout);
#endif
n=read();
for (i=1;i<=n;i++){
a[i].x=read(); a[i].y=read(); a[i].id=read();
}
sort(a+1,a+1+n,cmp);
++cnt;
b[1].x=-10000; b[1].y=-10000;
for (i=1;i<=n;i++){
if (a[i].id==1){
if (M[a[i].x]) continue;
M[a[i].x]=1;
Q.push(a[i].x);
}
}
while (!Q.empty()){
x=Q.front(); Q.pop();
for (i=1;i<=n;i++)
if (a[i].id==1 && a[i].x==x)
P.push(a[i].y);
++cnt;
b[cnt].x=x-0.1; b[cnt].y=-10000;
x=P.front(); P.pop();
++cnt;
b[cnt].x=b[cnt-1].x;
b[cnt].y=x+0.01;
++cnt;
b[cnt].x=b[cnt-1].x+0.1+0.01;
b[cnt].y=b[cnt-1].y;
++cnt;
b[cnt].x=b[cnt-1].x;
b[cnt].y=b[cnt-1].y-0.02;
++cnt;
b[cnt].x=b[cnt-1].x-0.1-0.005;
b[cnt].y=b[cnt-1].y;
while (!P.empty()){
x=P.front(); P.pop();
++cnt;
b[cnt].x=b[cnt-1].x;
b[cnt].y=x+0.01;
++cnt;
b[cnt].x=b[cnt-1].x+0.1+0.005;
b[cnt].y=b[cnt-1].y;
++cnt;
b[cnt].x=b[cnt-1].x;
b[cnt].y=b[cnt-1].y-0.02;
++cnt;
b[cnt].x=b[cnt-1].x-0.1-0.005;
b[cnt].y=b[cnt-1].y;
}
++cnt;
b[cnt].x=b[cnt-1].x;
b[cnt].y=-10000;
}
++cnt;
b[cnt].x=b[cnt-1].x;
b[cnt].y=b[cnt-1].y-1;
++cnt;
b[cnt].x=-10000;
b[cnt].y=b[cnt-1].y;
cout<<cnt<<endl;
for (i=1;i<=cnt;i++)
printf("%.5lf %.5lf\n",b[i].x,b[i].y);
cnt=1;
memset(b,0,sizeof(b));
b[1].x=b[1].y=10000;
M.clear();
for (i=n;i;i--){
if (a[i].id==2){
if (M[a[i].x]) continue;
M[a[i].x]=1; Q.push(a[i].x);
}
}
while (!Q.empty()){
x=Q.front(); Q.pop();
for (i=n;i;i--)
if (a[i].id==2 && a[i].x==x)
P.push(a[i].y);
++cnt;
b[cnt].x=x+0.1; b[cnt].y=10000;
x=P.front(); P.pop();
++cnt;
b[cnt].x=b[cnt-1].x;
b[cnt].y=x-0.01;
++cnt;
b[cnt].x=b[cnt-1].x-0.1-0.01;
b[cnt].y=b[cnt-1].y;
++cnt;
b[cnt].x=b[cnt-1].x;
b[cnt].y=b[cnt-1].y+0.02;
++cnt;
b[cnt].x=b[cnt-1].x+0.1+0.005;
b[cnt].y=b[cnt-1].y;
while (!P.empty()){
x=P.front(); P.pop();
++cnt;
b[cnt].x=b[cnt-1].x;
b[cnt].y=x-0.01;
++cnt;
b[cnt].x=b[cnt-1].x-0.1-0.005;
b[cnt].y=b[cnt-1].y;
++cnt;
b[cnt].x=b[cnt-1].x;
b[cnt].y=b[cnt-1].y+0.02;
++cnt;
b[cnt].x=b[cnt-1].x+0.1+0.005;
b[cnt].y=b[cnt-1].y;
}
++cnt;
b[cnt].x=b[cnt-1].x;
b[cnt].y=10000;
}
++cnt;
b[cnt].x=b[cnt-1].x;
b[cnt].y=b[cnt-1].y+1;
++cnt;
b[cnt].x=10000;
b[cnt].y=b[cnt-1].y;
cout<<cnt<<endl;
for (i=1;i<=cnt;i++)
printf("%.5lf %.5lf\n",b[i].x,b[i].y);
return 0;
}
[B] Buildings
题意
给出m面墙,每一面墙上有n \times n个墙砖,有c种颜色,问有多少种涂色方案.
题解
Polya定理.
代码
#include <cstdio>
#include <iostream>
#include <cmath>
using namespace std;
long long int n, m, c, ans, sum, k, mo = 1e9+7;
int gcd(int a, int b) {
if (b == 0) return a;
return gcd(b, a%b);
}
long long int mi(long long int a, long long int n) {
if (n == 0) return 1;
if (n == 1) return a;
long long int mid = mi(a, n/2);
mid = mid * mid % mo;
if (n%2) mid = mid * a % mo;
return mid;
}
int main() {
cin >> n >> m >> c;
k = mi(c, n*n);
sum = 0;
for (int i = 1; i <= m; i++) {
sum += mi(k, gcd(i, m));
}
sum %= mo;
ans = sum * mi(m, mo - 2) % mo;
cout << ans;
}
[C] Joyride
题意
给出一个游乐场地图,每一个点上都有一个游乐项目.参加游乐项目需要花费一定的时间和金钱.有一些边连接了一些点,走过每条边需要花费固定的事件.要求每经过一个点,都要游玩这个点的游乐项目.
现在要求从1号点出发,找到一条路线,使得在恰好消耗了x时间的情况下,花费最小.
题解
设f[i][j]表示在第i个点游玩完毕后,时间为j时的最小开销.
然后考虑在原地不动以及向周围移动的情况进行转移就行了.
代码
#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
#include<map>
#define l(x) (x<<1)
#define r(x) ((x<<1)|1)
#define IL inline
#define reg register
#define LL long long
#define N 1010
#define INF 0x3f3f3f3f3f3f3f3fll
using namespace std;
int n,m,i,t,j,k,x,y,lsum=1,s;
int head[N];
LL f[N][N];
struct Edge{
int t,next;
}e[N*8];
struct Data{
int x,y;
}a[N];
IL int Abs(int x){return (x<0)?-x:x;}
IL void Swap(int &a,int &b){a^=b^=a^=b;}
IL LL Min(LL a,LL b){return (a<b)?a:b;}
IL LL Max(LL a,LL b){return (a>b)?a:b;}
IL int read(){
int p=0,f=1; char c=getchar();
while (c<48||c>57) {if (c=='-') f=-1; c=getchar();}
while (c>=48&&c<=57) p=(p<<1)+(p<<3)+c-48,c=getchar();
return p*f;
}
inline void Add(int s,int t){
e[lsum].t=t; e[lsum].next=head[s]; head[s]=lsum++;
}
int main(){
#ifdef __Marvolo
freopen("zht.in","r",stdin);
freopen("zht.out","w",stdout);
#endif
s=read();
n=read(); m=read(); t=read();
for (i=1;i<=m;i++){
x=read(); y=read();
Add(x,y); Add(y,x);
}
for (i=1;i<=n;i++){
a[i].x=read(); a[i].y=read();
}
memset(f,INF,sizeof(f));
if (a[1].x>s){
puts("It is a trap.");
return 0;
}
if (a[1].x==s){
cout<<a[1].y<<endl;
return 0;
}
f[1][a[1].x]=a[1].y;
for (i=1;i<=s;i++)
for (j=1;j<=n;j++){
if (i>=t+a[j].x)
for (k=head[j];k;k=e[k].next){
if (f[e[k].t][i-t-a[j].x]!=INF)
f[j][i]=Min(f[j][i],f[e[k].t][i-t-a[j].x]+a[j].y);
}
if (i>=a[j].x)
if (f[j][i-a[j].x]!=INF)
f[j][i]=Min(f[j][i],f[j][i-a[j].x]+a[j].y);
}
if (f[1][s]==INF){
puts("It is a trap.");
}
else cout<<f[1][s]<<endl;
return 0;
}
[D] Pants On Fire
题意&题解
签到题
代码
#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
#include<map>
#define l(x) (x<<1)
#define r(x) ((x<<1)|1)
#define IL inline
#define reg register
#define LL long long
#define INF 0x3f3f3f3f
using namespace std;
int n,m,i,cnt,x,y,flag;
char c[110];
char s[500][110];
vector <int> son[500];
IL int Abs(int x){return (x<0)?-x:x;}
IL void Swap(int &a,int &b){a^=b^=a^=b;}
IL int Min(int a,int b){return (a<b)?a:b;}
IL int Max(int a,int b){return (a>b)?a:b;}
IL int read(){
int p=0,f=1; char c=getchar();
while (c<48||c>57) {if (c=='-') f=-1; c=getchar();}
while (c>=48&&c<=57) p=(p<<1)+(p<<3)+c-48,c=getchar();
return p*f;
}
IL int Insert(){
reg int i=0;
for (i=1;i<=cnt;i++){
if (strcmp(s[i],c)==0) return i;
}
++cnt;
for (i=0;i<=strlen(c);i++) s[cnt][i]=c[i];
return cnt;
}
IL int Find(){
reg int i=0;
for (i=1;i<=cnt;i++){
if (strcmp(s[i],c)==0) return i;
}
return -1;
}
IL void Dfs(int x,int p){
if (x==p){
flag=1;
return;
}
for (auto i : son[x]) Dfs(i,p);
}
int main(){
#ifdef __Marvolo
freopen("zht.in","r",stdin);
freopen("zht.out","w",stdout);
#endif
n=read(); m=read();
for (i=1;i<=n;i++){
scanf("%s",&c);
x=Insert();
scanf("%s",&c);scanf("%s",&c);scanf("%s",&c);
scanf("%s",&c);
y=Insert();
son[y].push_back(x);
}
for (i=1;i<=m;i++){
scanf("%s",&c);
x=Find();
scanf("%s",&c);scanf("%s",&c);scanf("%s",&c);
scanf("%s",&c);
y=Find();
if (x==-1 || y==-1){
puts("Pants on Fire");
continue;
}
if (x==y){
puts("Pants on Fire");
continue;
}
flag=0;
Dfs(y,x);
if (flag){
puts("Fact");
continue;
}
flag=0;
Dfs(x,y);
if (flag){
puts("Alternative Fact");
continue;
}
puts("Pants on Fire");
}
return 0;
}
[F] Plug It In
题意
有n个电器和m个插口,每一个电器只能插到固定的几个插口上.每个插口只能插一个电器.
有一个插线板,可以把一个插口变成三孔的.问在用插线板的情况下,至多给几个电器供电.
题解
显然是一个二分图模型.先不加插线板,跑一遍网络流,得到一个残量网络,然后尝试着在这个网络上添加一条边,也就是加上插线板,再在残量网络的基础上继续跑.枚举所有的插线板使用情况,取一个最大值就行了.
据说二分图上跑网络流的复杂度是O(n\sqrt{n})的,但是残量网络继续跑网络流的复杂度不太会算,因为sap算法需要重置一下gap和gaps数组.感觉上应该是O(n)就可以完成一路增广.
所以总的时间复杂度应该是O(n^{2}\sqrt{n}).
代码
#pragma GCC optimize(3)
#pragma comment(linker, "/STACK:102400000,102400000")
#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
#include<map>
#define l(x) (x<<1)
#define r(x) ((x<<1)|1)
#define IL inline
#define reg register
#define LL long long
#define N 6010
#define NN 75010
#define INF 0x3f3f3f3f
using namespace std;
int n,m,k,i,lsum=1,Lsum,x,y,cnt,Found,flow,al,Flow,Ans;
int head[N],Head[N],gap[N],gaps[N],Gap[N],Gaps[N];
struct Flow{
int t,next,fl,re;
}e[NN*8],E[NN*8];
IL int Abs(int x){return (x<0)?-x:x;}
IL void Swap(int &a,int &b){a^=b^=a^=b;}
IL int Min(int a,int b){return (a<b)?a:b;}
IL int Max(int a,int b){return (a>b)?a:b;}
IL int read(){
int p=0,f=1; char c=getchar();
while (c<48||c>57) {if (c=='-') f=-1; c=getchar();}
while (c>=48&&c<=57) p=(p<<1)+(p<<3)+c-48,c=getchar();
return p*f;
}
inline void Add(int s,int t,int fl){
e[lsum].t=t; e[lsum].fl=fl; e[lsum].next=head[s]; e[lsum].re=lsum+1; head[s]=lsum++;
e[lsum].t=s; e[lsum].fl=0; e[lsum].next=head[t]; e[lsum].re=lsum-1; head[t]=lsum++;
}
inline void Sap(int x){
int i=0,mingap=cnt-1,F=al;
if (x==cnt) {Found=1; flow+=al; return;}
for (i=head[x];i;i=e[i].next)
if (e[i].fl){
if (gap[e[i].t]+1==gap[x]){
al=Min(al,e[i].fl); Sap(e[i].t);
if (gap[1]>=cnt) return;
if (Found) break;
al=F;
}
mingap=Min(mingap,gap[e[i].t]);
}
if (!Found){
gaps[gap[x]]--; if (!gaps[gap[x]]) gap[1]=cnt;
gaps[gap[x]=mingap+1]++;
} else e[i].fl-=al,e[e[i].re].fl+=al;
}
int main(){
#ifdef __Marvolo
freopen("zht.in","r",stdin);
freopen("zht.out","w",stdout);
#endif
m=read(); n=read(); k=read();
cnt=n+m+2;
for (i=1;i<=k;i++){
x=read(); y=read();
Add(1+y,1+n+x,1);
}
for (i=1;i<=n;i++) Add(1,1+i,1);
for (i=1;i<=m;i++) Add(1+n+i,cnt,1);
gaps[0]=cnt;
while (gap[1]<cnt){
al=INF; Found=0; Sap(1);
}
Ans=flow;
Lsum=lsum; Flow=flow;
memcpy(E,e,sizeof(e[0])*(lsum+5));
memcpy(Head,head,sizeof(head[0])*(n+m+5));
for (i=1;i<=m;i++){
lsum=Lsum; flow=Flow;
memcpy(e,E,sizeof(e[0])*(lsum+5));
memcpy(head,Head,sizeof(head[0])*(n+m+5));
memset(gap,0,sizeof(gap));
memset(gaps,0,sizeof(gaps));
Add(1+n+i,cnt,2);
gaps[0]=cnt;
while (gap[1]<cnt){
al=INF; Found=0; Sap(1);
}
Ans=Max(Ans,flow);
}
cout<<Ans<<endl;
return 0;
}
[G] Water Testing
题意
给出平面上一个多边形,求其内部有多少个整点.
题解
Pick定理裸题
代码
#include <iostream>
template <typename T>
T gcd(T __a, T __b)
{
T __tp;
while (__b)
{
__tp = __a % __b;
__a = __b;
__b = __tp;
}
return __a;
}
using namespace std;
#define LL long long
#define ULL unsigned LL
#define GC getchar()
#define PC putchar
#define _Q_(x) {register char _c=GC,_v=1;for(x=0;_c<48||_c>57;_c=GC)if(_c==45)_v=-1;
#define _H_(x) for(;_c>=48&&_c<=57;x=(x<<1)+(x<<3)+_c-48,_c=GC);if(_v==-1)x=-x;}
#define sc(x) _Q_(x)_H_(x)
template<class T>
void UPRT(const T _){if(_>=10)UPRT(_/10);PC(_%10+48);}
#define UPL(_) UPRT(_),PC(10)
template<class T>
void PRT(const T _){if(_<0){PC(45),UPRT<ULL>(-(ULL)_);return;}if(_>=10)PRT(_/10);PC(_%10+48);}
#define PL(_) PRT(_),PC(10)
constexpr int MN(1e5+7);
LL x[MN], y[MN];
signed main()
{
int n;
sc(n)
for (int i=0; i<n; ++i)
{
sc(x[i])sc(y[i])
}
long long ssum = 0, csum = 0;
for (int i=0; i<n; ++i)
{
int ii = i+1;
if (ii == n)
ii = 0;
ssum += x[i]*y[ii]-x[ii]*y[i];
auto dx = x[i]>x[ii] ? x[i]-x[ii]:x[ii]-x[i];
auto dy = y[i]>y[ii] ? y[i]-y[ii]:y[ii]-y[i];
auto cnt = gcd(dx, dy);
csum += cnt;
}
if (ssum < 0)
ssum = -ssum;
auto sum = ssum - csum + 2;
PRT(sum/2);
}
[I] Uberwatch
题意&题解
dp
签到题
代码
#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
#include<map>
#include<queue>
#define l(x) (x<<1)
#define r(x) ((x<<1)|1)
#define IL inline
#define reg register
#define LL long long
#define INF 0x3f3f3f3f
using namespace std;
int n,m,i;
int a[300010],f[300010];
priority_queue <int> Q;
IL int Abs(int x){return (x<0)?-x:x;}
IL void Swap(int &a,int &b){a^=b^=a^=b;}
IL int Min(int a,int b){return (a<b)?a:b;}
IL int Max(int a,int b){return (a>b)?a:b;}
IL int read(){
int p=0,f=1; char c=getchar();
while (c<48||c>57) {if (c=='-') f=-1; c=getchar();}
while (c>=48&&c<=57) p=(p<<1)+(p<<3)+c-48,c=getchar();
return p*f;
}
int main(){
#ifdef __Marvolo
freopen("zht.in","r",stdin);
freopen("zht.out","w",stdout);
#endif
n=read(); m=read();
for (i=1;i<=n;i++) a[i]=read();
for (i=1;i<=n;i++) f[i]=-INF;
f[1]=0;
for (i=1+m;i<=n;i++){
Q.push(f[i-m]);
if (i>=m){
int x=Q.top();
f[i]=x+a[i];
}
}
int Ans=-INF;
for (i=1;i<=n;i++) Ans=Max(Ans,f[i]);
cout<<Ans<<endl;
return 0;
}
[K] You Are Fired
题意&题解
签到题
代码
#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
#include<map>
#define l(x) (x<<1)
#define r(x) ((x<<1)|1)
#define IL inline
#define reg register
#define LL long long
#define N 10010
#define INF 0x3f3f3f3f
using namespace std;
int n,d,k,i;
struct Data{
char s[10];
int x;
}a[N];
IL int Abs(int x){return (x<0)?-x:x;}
IL void Swap(int &a,int &b){a^=b^=a^=b;}
IL int Min(int a,int b){return (a<b)?a:b;}
IL int Max(int a,int b){return (a>b)?a:b;}
IL bool cmp(Data a,Data b){return a.x>b.x;}
IL int read(){
int p=0,f=1; char c=getchar();
while (c<48||c>57) {if (c=='-') f=-1; c=getchar();}
while (c>=48&&c<=57) p=(p<<1)+(p<<3)+c-48,c=getchar();
return p*f;
}
int main(){
#ifdef __Marvolo
freopen("zht.in","r",stdin);
freopen("zht.out","w",stdout);
#endif
n=read(); d=read(); k=read();
for (i=1;i<=n;i++){
scanf("%s",&a[i].s);
scanf("%d",&a[i].x);
}
sort(a+1,a+1+n,cmp);
int ans=0;
for (i=1;i<=k;i++){
ans+=a[i].x;
}
if (ans<d){
puts("impossible");
return 0;
} else {
printf("%d\n",k);
for (i=1;i<=k;i++)
printf("%s, YOU ARE FIRED!\n",a[i].s);
}
return 0;
}
声明:
本文采用
BY-NC-SA
协议进行授权，如无注明均为原创，转载请注明转自
Marvolo
本文地址: ACM-ICPC GCPC 2017部分题解
本文地址: ACM-ICPC GCPC 2017部分题解
