lemonoil

OI__nothing is impossible

杂题---NOI

• 标签: 杂题 NOI

救生员的小小问题

Description 七濑遥作为游泳池的救生员，他正在池边游荡，突然看到一个小女孩落水了！他必须立刻行动！ 七濑遥工作的泳池是一个凸 n 边形，他在地面上单位距离移动的时间为 tg，在水中单位距离移动的时间为 tw。因为七濑遥有特殊的入水技巧，所以入水和上岸不需要时间。一开始七濑遥站在多边形的边上，而小女孩在多边形的内部。 Task Input 第一行一个整数 n。 第二行 n 对整数 (xi, yi) 表示多边形顶点的坐标，按逆时针排列。 接下来一行一个整数 tg。 接下来一行一个整数 tw。 接下来一行两个整数 (xs, ys) 表示七濑遥的位置，保证在多边形的边上。 接下来一行两个整数 (xt, yt) 表示小女孩的位置，保证在多边形的内部。 Output 输出一个浮点数表示最短时间，四舍五入保留 6 位小数。 Sample I Input 4 0 0 10 0 10 10 0 10 10 12 0 5 9 5 Output 108.000000 Sample II Input 4 0 0 10 0 10 10 0 10 10 12 0 0 9 1 Output 96.633250 Sample III Input 4 0 0 10 0 10 10 0 10 10 12 0 1 9 1 Output 103.266499 Sample IV Input 8 2 0 4 0 6 2 6 4 4 6 2 6 0 4 0 2 10 12 3 0 3 5 Output 60.000000 Constraint 对于 100% 的数据，3≤n≤10，−100≤xi, yi, xs, ys, xt, yt≤100，1≤tg<tw≤100。

code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
//orz 又短又快。。。
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
typedef double ldb;
const ldb eps=1e-8;
int n,dx[20],dy[20],tg,tw;
int sx,sy,tx,ty,bg;
ldb ans=1e20,dis=0,lstx,lsty;
int cross(int x1,int y1,int x2,int y2,int x,int y){
	return (x2-x1)*(y-y1)-(y2-y1)*(x-x1);
}
int inline nxt(int x){
	return x==n?1:x+1;
}
int inline lst(int x){
	return x==1?n:x-1;
}
ldb dist(ldb x1,ldb y1,ldb x2,ldb y2){
	return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
}
ldb calc(ldb x,ldb y,ldb x1,ldb y1){
	return dist(x,y,x1,y1)*tg+dist(x1,y1,tx,ty)*tw;
}
ldb solve(int x1,int y1,int x2,int y2,int x,int y){
	ldb lx=x1,ly=y1,rx=x2,ry=y2;
	while(fabs(lx-rx)>eps||fabs(ly-ry)>eps){
		ldb x1=(lx+lx+rx)/3.0,y1=(ly+ly+ry)/3.0;
		ldb x2=(lx+rx+rx)/3.0,y2=(ly+ry+ry)/3.0;
		ldb ans1=calc(x,y,x1,y1),ans2=calc(x,y,x2,y2);
		if(ans1>ans2)lx=x1,ly=y1;
		else rx=x2,ry=y2;
	}
	return calc(x,y,lx,ly);
}
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;++i)
		scanf("%d%d",&dx[i],&dy[i]);
	scanf("%d%d%d%d%d%d",&tg,&tw,&sx,&sy,&tx,&ty);
	for(int i=1;i<=n;++i)
		if(cross(dx[i],dy[i],dx[nxt(i)],dy[nxt(i)],sx,sy)==0){bg=i;break;}
	ans=min(ans,solve(dx[bg],dy[bg],dx[nxt(bg)],dy[nxt(bg)],lstx=sx,lsty=sy));
	for(int i=nxt(bg);i!=bg;i=nxt(i)){
		dis+=dist(dx[i],dy[i],lstx,lsty);
		ans=min(ans,solve(dx[i],dy[i],dx[nxt(i)],dy[nxt(i)],lstx=dx[i],lsty=dy[i])+dis*tg);
	}
	dis=0,lstx=sx,lsty=sy;
	for(int i=lst(bg);i!=bg;i=lst(i)){
		dis+=dist(dx[nxt(i)],dy[nxt(i)],lstx,lsty);
		ans=min(ans,solve(dx[nxt(i)],dy[nxt(i)],dx[i],dy[i],lstx=dx[nxt(i)],lsty=dy[nxt(i)])+dis*tg);
	}
	printf("%.6lf",ans);
}

新司机的小小问题

Description 最近周日天同学因为资金短缺，当起了兼职司机。

有 N 个点，M 个乘客。日天用一款叫“dada”的 app 知道了每个人的出行计划。乘客 i 会在 Ti 时刻在 Ai 上车，下车地点为 Bi。设其乘车时间为 Si，则乘客 i 会支付 max{0, Pi−Si}。日天的出租车最多可以同时坐 K 个人（不包括司机），他 0 时刻在 1 号点。

求日天同学最多能赚多少钱。

Task Input

第一行有 3 个整数 N, M, K。

接下来 M 行，每行 4 个整数 Ti, Ai, Bi, Pi。

接下来一个 N×N 的整数矩阵，Dij 表示从 i 号点到 j 号点要花的时间。

Output

输出一个整数表示日天同学最多能赚多少钱。

Sample I Input

3 2 1 1 1 3 10 2 2 1 100 0 1 2 1 0 2 2 2 0 Output

99 Sample II Input

2 2 2 2 1 2 100 50 2 1 1000 0 50 50 0 Output

950 Sample III Input

2 2 2 2 1 2 100 50 2 1 1000 0 48 50 0 Output

1002 Constraint 对于 10% 的数据，K=1。

对于 100% 的数据，1≤N, M≤20，1≤K≤4，Ti<Ti+1，1≤Ai, Bi≤N, Ai≠Bi，0≤Pi≤1000，0≤Dij≤100，Dii=0。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cctype>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <deque>
#include <fstream>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <memory.h>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>
#define ls (oo << 1)
#define rs (oo << 1 | 1)
#define mid ((L + R) / 2)
using namespace std;
typedef long long LL;
#define clr(a, x) memset(a, x, sizeof a)
const int MAXN = 25;
const int MAXM = 7005;
struct Node {
    int t, x, y, p;
    bool operator<(const Node &a) const { return t < a.t; }
};
Node a[MAXN];
int G[MAXN][MAXN];
int idx[MAXM], state[1 << 20], num[MAXM], cnt;
int dp[20][MAXM];
int S[5], vis[5], top;
int n, m, K;
int ans;
void dfs(int cur, int x, int s) {
    if (cur > K)
        return;
    if (x == m) {
        idx[cnt] = s;
        num[cnt] = cur;
        state[s] = cnt++;
        return;
    }
    dfs(cur, x + 1, s << 1);
    dfs(cur + 1, x + 1, s << 1 | 1);
}
void dfs2(int cur, int now, int val, int pos, int s, int x) {
    if (cur == top) {
        if (s == 0)
            ans = max(ans, val);
        for (int i = x; i < m; ++i) {
            int k = state[s | (1 << i)];
            if (now + G[pos][a[i].x] <= a[i].t)
                dp[i][k] = max(dp[i][k], val);
        }
        return;
    }
    for (int i = 0; i < top; ++i)
        if (!vis[i]) {
            vis[i] = 1;
            int v = S[i], nxt = now + G[pos][a[v].y];
            dfs2(cur + 1, nxt, val + max(a[v].p + a[v].t - nxt, 0), a[v].y, s,
                 x);
            vis[i] = 0;
        }
}
void solve() {
    cnt = 0;
    scanf("%d%d%d", &n, &m, &K);
    dfs(0, 0, 0);
    for (int i = 0; i < m; ++i) {
        scanf("%d%d%d%d", &a[i].t, &a[i].x, &a[i].y, &a[i].p);
        a[i].x--;
        a[i].y--;
    }
    sort(a, a + m);
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            scanf("%d", &G[i][j]);
        }
    }
    for (int k = 0; k < n; ++k) { // floyd
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                G[i][j] = min(G[i][j], G[i][k] + G[k][j]);
            }
        }
    }
    clr(dp, -1);
    ans = 0;
    for (int i = 0; i < m; ++i) {
        if (G[0][a[i].x] <= a[i].t)
            dp[i][state[1 << i]] = max(dp[i][state[1 << i]], 0);
        for (int j = 1; j < cnt; ++j)
            if (dp[i][j] != -1) {
                int st = idx[j];
                for (int k = st; ~k; k = k ? (st & (k - 1)) : -1) {
                    top = 0;
                    int tmp = 0;
                    for (int l = 0; l < m; ++l) {
                        if (k & (1 << l))
                            S[top++] = l;
                        else if (st & (1 << l))
                            ++tmp;
                    }
                    if (tmp < K)
                        dfs2(0, a[i].t, dp[i][j], a[i].x, st ^ k, i + 1);
                }
            }
    }
    printf("%d\n", ans);
}
int main() {
    freopen("Taxi.in","r", stdin);
    freopen("Taxi.out","w", stdout);
    solve();
    return 0;
}

龙女仆的小小问题

Description 康娜是一个聪明的小孩，经常玩一些益智游戏。但她并不满足于玩别人发明的游戏，她也想着创造一些新的游戏玩法。

某日，康娜灵机一动，又想到了一个数学游戏并且编写了程序给大家玩。首先给定一个整数 M，接着系统随机排列 0 到 M−1 之间的不重复的 M 个数。假设这 M 个数保存在数组 A 中，接着系统给出一个大小也为 M 的数组 B，以及一个非负整数 D。

游戏开始后，每一轮玩家只能执行下面的其中一种操作：

从当前未被选择的数中选一个数 Ai 作为“当前数”，付出 Bi 的代价。 设“当前数”为 Ai，对于任意还未被选择的 Aj，如果 j>i 并且存在最小的非负整数 k 使得 Aj≡Ai⋅Dk(modM)，就可以选择 Aj 作为“当前数”，付出 k(Aj+1) 的代价。 注意：

第一轮玩家只能进行操作 1。 对于操作 2，假设 00=1。 游戏的目标是选完所有数，并且代价最小。

Task Input

第一行有两个整数 M, D。

接着一行有 M 个数，表示数组 A 中的 M 个数。

接着一行有 M 个数，表示数组 B 中的 M 个数。

Output

输出通过游戏的最小代价。

Sample I Input

3 2 0 2 1 10 20 30 Output

32 Explanation

先用操作 1 选择 0，再用操作 1 选择 2，再用操作 2 选择 1，10+20+2=32。

Sample II Input

3 3 1 2 0 1 5 3 Output

7 Explanation

先用操作 1 选择 1，再用操作 2 选择 0，再用操作 1 选择 2，1+1+5=7。

Constraint 对于 100% 的数据，1≤M≤100，0≤D≤109，0≤Bi≤100。

code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
//orz root 大佬强无敌
#define _GLIBCXX_IOSTREAM
#include<bits/stdc++.h>
typedef unsigned int uint;
typedef long long ll;
typedef unsigned long long ull;
typedef double lf;
typedef long double llf;
typedef std::pair<int,int> pii;
#define xx first
#define yy second
template<typename T> inline T max(T a,T b){return a>b?a:b;}
template<typename T> inline T min(T a,T b){return a<b?a:b;}
template<typename T> inline T abs(T a){return a>0?a:-a;}
template<typename T> inline bool repr(T &a,T b){return a<b?a=b,1:0;}
template<typename T> inline bool repl(T &a,T b){return a>b?a=b,1:0;}
template<typename T> inline T gcd(T a,T b){T t;if(a<b){while(a){t=a;a=b%a;b=t;}return b;}else{while(b){t=b;b=a%b;a=t;}return a;}}
template<typename T> inline T sqr(T x){return x*x;}
#define mp(a,b) std::make_pair(a,b)
#define pb push_back
#define I inline
#define mset(a,b) memset(a,b,sizeof(a))
#define mcpy(a,b) memcpy(a,b,sizeof(a))
#define fo0(i,n) for(int i=0,i##end=n;i<i##end;i++)
#define fo1(i,n) for(int i=1,i##end=n;i<=i##end;i++)
#define fo(i,a,b) for(int i=a,i##end=b;i<=i##end;i++)
#define fd0(i,n) for(int i=(n)-1;~i;i--)
#define fd1(i,n) for(int i=n;i;i--)
#define fd(i,a,b) for(int i=a,i##end=b;i>=i##end;i--)
#define foe(i,x)for(__typeof(x.end())i=x.begin();i!=x.end();++i)
struct Cg{I char operator()(){return getchar();}};
struct Cp{I void operator()(char x){putchar(x);}};
#define OP operator
#define RT return *this;
#define RX x=0;char t=P();while((t<'0'||t>'9')&&t!='-')t=P();bool f=0;\
if(t=='-')t=P(),f=1;x=t-'0';for(t=P();t>='0'&&t<='9';t=P())x=x*10+t-'0'
#define RL if(t=='.'){lf u=0.1;for(t=P();t>='0'&&t<='9';t=P(),u*=0.1)x+=u*(t-'0');}if(f)x=-x
#define RU x=0;char t=P();while(t<'0'||t>'9')t=P();x=t-'0';for(t=P();t>='0'&&t<='9';t=P())x=x*10+t-'0'
#define TR *this,x;return x;
I bool IS(char x){return x==10||x==13||x==' ';}template<typename T>struct Fr{T P;I Fr&OP,(int &x)
{RX;if(f)x=-x;RT}I OP int(){int x;TR}I Fr&OP,(ll &x){RX;if(f)x=-x;RT}I OP ll(){ll x;TR}I Fr&OP,(char &x)
{for(x=P();IS(x);x=P());RT}I OP char(){char x;TR}I Fr&OP,(char *x){char t=P();for(;IS(t);t=P());if(~t){
for(;!IS(t)&&~t;t=P())*x++=t;}*x++=0;RT}I Fr&OP,(lf &x){RX;RL;RT}I OP lf(){lf x;TR}I Fr&OP,(llf &x){RX;RL;RT}I OP llf(){llf x;TR}
I Fr&OP,(uint &x){RU;RT}I OP uint(){uint x;TR}I Fr&OP,(ull &x){RU;RT}I OP ull(){ull x;TR}};Fr<Cg>in;
#define WI(S) if(x){if(x<0)P('-'),x=-x;char s[S],c=0;while(x)s[c++]=x%10+'0',x/=10;while(c--)P(s[c]);}else P('0')
#define WL if(y){lf t=0.5;for(int i=y;i--;)t*=0.1;if(x>=0)x+=t;else x-=t,P('-');*this,(ll)(abs(x));P('.');if(x<0)x=-x;\
while(y--){x*=10;x-=floor(x*0.1)*10;P(((int)x)%10+'0');}}else if(x>=0)*this,(ll)(x+0.5);else *this,(ll)(x-0.5);
#define WU(S) if(x){char s[S],c=0;while(x)s[c++]=x%10+'0',x/=10;while(c--)P(s[c]);}else P('0')
template<typename T>struct Fw{T P;I Fw&OP,(int x){WI(10);RT}I Fw&OP()(int x){WI(10);RT}I Fw&OP,(uint x){WU(10);RT}
I Fw&OP()(uint x){WU(10);RT}I Fw&OP,(ll x){WI(19);RT}I Fw&OP()(ll x){WI(19);RT}I Fw&OP,(ull x){WU(20);RT}
I Fw&OP()(ull x){WU(20);RT}I Fw&OP,(char x){P(x);RT}I Fw&OP()(char x){P(x);RT}I Fw&OP,(const char *x){while(*x)P(*x++);RT}
I Fw&OP()(const char *x){while(*x)P(*x++);RT}I Fw&OP()(lf x,int y){WL;RT}I Fw&OP()(llf x,int y){WL;RT}};Fw<Cp>out;
const int N=205,M=400000,Nf=255;
struct edge
{
	int to,w,ne,v;
}e[M*2+2];
int p[N+1],em=2,q[N<<1],qe,fa[N+1],dis[N+1];
bool vis[N+1];
inline void add(int a,int b,int w,int v)
{
	e[em].to=b,e[em].w=w,e[em].v=v,e[em].ne=p[a],p[a]=em++;
	e[em].to=a,e[em].w=0,e[em].v=-v,e[em].ne=p[b],p[b]=em++;
}
inline int wxhcoder(int s,int t,int &cost)
{
	cost=0;
	int flow=0;
	while(1)
	{
		memset(dis,0x3f,sizeof(dis));
		memset(fa,0x3f,sizeof(fa));
		dis[s]=0; 
		vis[s]=1;
		q[0]=s,qe=1;
		for(int i=0;i^qe;i++)
		{
			int k=q[i&Nf];
			for(int j=p[k];j;j=e[j].ne)
				if(e[j].w&&dis[e[j].to]>dis[k]+e[j].v)
				{
					dis[e[j].to]=dis[k]+e[j].v;
					fa[e[j].to]=j^1;
					if(!vis[e[j].to])q[(qe++)&Nf]=e[j].to,vis[e[j].to]=1;
				}
			vis[k]=0;
		}
		if(fa[t]==0x3f3f3f3f)break;
		int rfl=0x7fffffff;
		for(int i=t;i!=s;i=e[fa[i]].to)
			repl(rfl,e[fa[i]^1].w);
		cost+=dis[t]*rfl;
		flow+=rfl;
		for(int i=t;i!=s;i=e[fa[i]].to)
			e[fa[i]].w+=rfl,e[fa[i]^1].w-=rfl;
	}
	return flow;
}
int n,m,a[100],b[100],g[100];
int main()
{
	in,n,m;
	fo0(i,n)in,a[i];
	fo0(i,n)in,b[i];
	int S=n*2,T=n*2+1;
	fo0(i,n)add(S,i,1,0);
	fo0(i,n)add(i+n,T,1,0);
	fo0(i,n)
	{
		mset(g,0xff);
		for(int x=a[i],j=0;!~g[x];x=(ll)x*m%n,j++)
			g[x]=j;
		fo(j,i+1,n-1)if(~g[a[j]])add(i,j+n,1,g[a[j]]*(a[j]+1));
	}
	fo0(i,n)add(S,i+n,1,b[i]);
	int cost,flow=wxhcoder(S,T,cost);
	out,cost,'\n';
}

click it and link me

Launch CodeCogs Equation Editor