题意:在一个圆上有n个点和链接两个点的一座桥,每个点在不同月份有不同的权值。要求回答q次询问每次询问给出月份m和两个点u,v,要求输出起点为u,终点为v的经历每个点仅一次的权值最大路径。
用c++写的
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
const int N = 100010;
int n,m,p,q,month; //n表示有n棵花树,m为观赏方案的种类,p和q之间有一座桥
int a[13][N];
int hh[13][N]; //hh[13][N]为前缀和,用来求u到v途中经过的开花的树的数量
int len(int u,int v) //len(u,v)为u按顺时针方向走到v的途中经过的开花的树的数量
{
if (u <= v) return hh[month][v] - hh[month][u - 1];
else return hh[month][n] - hh[month][u - 1] + hh[month][v];
}
void solve()
{
for (int i = 1; i <= n; i++)
{
int x;
scanf("%d", &x);
if (x == 1)
{
a[1][i]++;
a[2][i]++;
a[3][i]++;
}
else if (x == 2)
{
a[3][i]++;
a[4][i]++;
}
else if (x == 3)
{
a[4][i]++;
a[5][i]++;
}
else if (x == 4)
{
a[9][i]++;
a[10][i]++;
}
}
for (int i = 1; i <= n; i++)
for (int j = 1; j <= 12; j++)
hh[j][i] = hh[j][i - 1] + a[j][i]; //前缀和
scanf("%d%d%d", &p, &q, &m);
if (p > q) swap(p, q);
for (int i = 1; i <= m; i++)
{
int u, v, ans;
scanf("%d%d%d", &month, &u, &v);
if (u > v) swap(u, v);
bool flag = (u > p && u < q);
bool check = (v > p && v < q);
if (u == p || u == q || v == p || v == q) //只要有点在桥上面时一定不走桥最优
ans = max(len(u, v), len(v, u));
else if (flag && check) //两点处同一区域时一定不走桥最优
ans = max(len(u, v), len(v, u));
else if(!flag && !check) //两点处同一区域一定不走桥最优
ans = max(len(u, v), len(v, u));
else if (flag) //u,v在桥两边且u > p && u < q
ans = max({len(u, v), len(v, u), len(q, v) + len(p, u), len(u, q) + len(v, p)});
else if (check) //u,v在桥两边且v > p && v < q
ans = max({len(u, v), len(v, u), len(u, p) + len(v, q), len(q, u) + len(p, v)});
if (ans)
printf("%d\n", ans);
else
printf("So Sad.\n");
}
}
int main()
{
while (scanf("%d", &n) == 1)
{
solve();
}
return 0;
}
用c语言写的
#include<stdio.h>
int n,m,p,q,month; //n表示有n棵花树,m为观赏方案的种类,p和q之间有一座桥
int a[13][100010]; //a[month][i]表示点i在month月的权值
int hh[13][100010]; //hh[month][i]表示点1~i在month月的权值和,用前缀和思想来求u到v途中经过的开花的树的数量
void swap(int x,int y)
{
int k = 0;
k = p;
p = q;
q = k;
}
int len(int u,int v) //len(u,v)为u按顺时针方向走到v的途中经过的开花的树的数量(权值和)
{
if (u <= v) return hh[month][v] - hh[month][u - 1];
else return hh[month][n] - hh[month][u - 1] + hh[month][v];
}
void solve()
{
for (int i = 1; i <= n; i++)
{
int x;
scanf("%d", &x);
if (x == 1)
{
a[1][i]++;
a[2][i]++;
a[3][i]++;
}
else if (x == 2)
{
a[3][i]++;
a[4][i]++;
}
else if (x == 3)
{
a[4][i]++;
a[5][i]++;
}
else if (x == 4)
{
a[9][i]++;
a[10][i]++;
}
}
for (int i = 1; i <= n; i++)
for (int j = 1; j <= 12; j++)
hh[j][i] = hh[j][i - 1] + a[j][i]; //求前缀和
scanf("%d%d%d", &p, &q, &m);
if (p > q) swap(p, q);
for (int i = 1; i <= m; i++)
{
int u, v, ans;
scanf("%d%d%d", &month, &u, &v);
if (u > v) swap(u, v);
if (u == p || u == q || v == p || v == q) //只要有点在桥上面时一定不走桥最优
ans = (len(u, v)>=len(v, u)?len(u,v):len(v,u));
else if ((u > p && u < q) && (v > p && v < q)) //两点处同一区域时一定不走桥最优
ans = (len(u, v)>=len(v, u)?len(u,v):len(v,u));
else if(!(u > p && u < q) && !(v > p && v < q)) //两点处同一区域一定不走桥最优
ans = (len(u, v)>=len(v, u)?len(u,v):len(v,u));
else if (u > p && u < q) //u,v在桥两边且u > p && u < q(情况二)
{
ans = len(u,v);
if(len(v, u) > ans) ans = len(v, u);
if((len(q, v) + len(p, u)) > ans) ans = len(q, v) + len(p, u);
if((len(u, q) + len(v, p)) > ans) ans = len(u, q) + len(v, p);
}
else if (v > p && v < q) //u,v在桥两边且v > p && v < q(情况一)
{
ans = len(u,v);
if((len(v, u)) > ans) ans = len(v, u);
if((len(u, p) + len(v, q)) > ans) ans = len(u, p) + len(v, q);
if((len(q, u) + len(p, v)) > ans) ans = len(q, u) + len(p, v);
}
if (ans)
printf("%d\n", ans);
else
printf("So Sad.\n");
}
}
int main()
{
while (scanf("%d", &n) == 1) //n为0的时候结束,否则可以一直读
{
solve();
}
return 0;
}
输入数据:
10
1 1 2 4 3 2 4 4 3 3
3 9
5
1 1 5
1 3 9
3 5 10
7 1 10
10 2 9
输出数据:
2
2
4
So Sad.
3