2017-2018 ACM-ICPC Southwestern European Regional Programming Contest (SWERC 2017)
A. Cakey McCakeFace
按題意模擬即可。
#include<stdio.h>
#include<iostream>
#include<string.h>
#include<string>
#include<ctype.h>
#include<math.h>
#include<set>
#include<map>
#include<vector>
#include<queue>
#include<bitset>
#include<algorithm>
#include<time.h>
using namespace std;
void fre() { }
#define MS(x, y) memset(x, y, sizeof(x))
#define ls o<<1
#define rs o<<1|1
typedef long long LL;
typedef unsigned long long UL;
typedef unsigned int UI;
template <class T1, class T2>inline void gmax(T1 &a, T2 b) { if (b > a)a = b; }
template <class T1, class T2>inline void gmin(T1 &a, T2 b) { if (b < a)a = b; }
const int N = 0, M = 0, Z = 1e9 + 7, inf = 0x3f3f3f3f;
template <class T1, class T2>inline void gadd(T1 &a, T2 b) { a = (a + b) % Z; }
int casenum, casei;
int n, m;
int a[2005], b[2005];
int main()
{
while(~scanf("%d%d",&n, &m))
{
for(int i = 1; i <= n; ++i)
{
scanf("%d", &a[i]);
}
for(int i = 1; i <= m; ++i)
{
scanf("%d", &b[i]);
}
map<int,int>mop;
int cnt = -1, val;
for(int i = 1; i <= n; ++i)
{
for(int j = 1; j <= m; ++j)if(b[j] >= a[i])
{
++mop[b[j] - a[i]];
}
}
for(auto it : mop)
{
if(it.second > cnt)
{
cnt = it.second;
val = it.first;
}
}
printf("%d\n", val);
}
return 0;
}
/*
【trick&&吐槽】
【題意】
【分析】
【時間復雜度&&優化】
*/
B. Table
枚舉下底邊，求出每個位置向上延伸的最大長度，枚舉每個位置作為右下角，那么單調棧中每一個子矩形都可以對長寬都不超過它的詢問產生貢獻，通過差分二維前綴和，那么$O(1)$單點修改即可。
為了避免枚舉單調棧中每一項，可以在每一項退棧時計算有多少個右下角可以與它產生貢獻，這是對差分后的二維前綴和的一段區間加，再次差分前綴和轉化成單點修改即可。
時間復雜度$O(xy+n+d)$。
#include<cstdio>
const int N=2010;
int n,m,_a,_b,i,j,a[N][N],b[N][N],f[N],q[N],t;
inline void work(int x,int y,int z,int o){
/*for(int i=y;i<=z;i++){
b[i-y][o]--;
b[i+1-x][o]++;
}
return;*/
b[0][o]--;
b[z-y+1][o]++;
b[y+1-x][o]++;
b[z+1-x+1][o]--;
}
int main(){
scanf("%d%d%d%d",&n,&m,&_a,&_b);
while(_a--){
int xl,xr,yl,yr;
scanf("%d%d%d%d",&xl,&xr,&yl,&yr);
a[xr][yr]++;
a[xl][yr]--;
a[xr][yl]--;
a[xl][yl]++;
}
for(i=n;i;i--)for(j=m;j;j--)a[i][j]+=a[i+1][j]+a[i][j+1]-a[i+1][j+1];
for(i=1;i<=n;i++)for(j=1;j<=m;j++)a[i][j]=a[i][j]==0;
/*puts("");
for(i=1;i<=n;i++){
for(j=1;j<=m;j++)printf("%d",a[i][j]);
puts("");
}*/
for(i=1;i<=n;i++){
for(j=1;j<=m;j++)if(a[i][j])f[j]++;else f[j]=0;
for(q[t=0]=0,j=1;j<=m;q[++t]=j++){
while(t&&f[j]<f[q[t]]){
work(q[t-1]+1,q[t],j-1,f[q[t]]);
t--;
}
}
for(j=1;j<=t;j++)work(q[j-1]+1,q[j],m,f[q[j]]);
}
for(j=1;j<=n;j++)for(i=1;i<=m+5;i++)b[i][j]+=b[i-1][j];
for(i=m;i;i--)for(j=n;j;j--)b[i][j]+=b[i+1][j]+b[i][j+1]-b[i+1][j+1];
while(_b--)scanf("%d%d",&i,&j),printf("%d\n",b[j][i]);
}
/*
7 5 3 9
1 2 0 1
5 7 2 5
0 1 2 4
7 1
3 5
5 3
2 2
3 3
4 4
4 5
6 2
1 1
*/
C. Macarons
設$f[i][S]$表示考慮前$i$行，第$i$行每個位置是否被填充的情況為$S$的合法方案數。
逐格轉移預處理出轉移矩陣后快速冪即可。
時間復雜度$O(2^{3n}\log m)$。
#include<cstdio>
#define rep(i) for(int i=0;i<m;i++)
typedef long long ll;
const int N=260,P=1000000000;
int n,m,S,i,j,k,x,y,z,f[N],g[N];
ll K;
int A[N][N],B[N][N],C[N][N];
inline void up(int&a,int b){a=a+b<P?a+b:a+b-P;}
inline void mul(int A[][N],int B[][N],int F[][N]){
rep(i)rep(j)C[i][j]=0;
rep(i)rep(j)if(A[i][j])rep(k)if(B[j][k])C[i][k]=(1LL*A[i][j]*B[j][k]+C[i][k])%P;
rep(i)rep(j)F[i][j]=C[i][j];
}
int main(){
scanf("%d%lld",&n,&K);
m=1<<n;
for(S=0;S<m;S++){
for(j=0;j<m;j++)f[j]=g[j]=0;
f[S]=1;
for(i=0;i<n;i++){
for(j=0;j<m;j++)g[j]=0;
for(j=0;j<m;j++)if(f[j]){
if(!(j>>i&1)){
up(g[j^(1<<i)],f[j]);
}else{
up(g[j^(1<<i)],f[j]);
up(g[j],f[j]);
if(i&&!(j>>(i-1)&1))up(g[j|(1<<(i-1))],f[j]);
}
}
for(j=0;j<m;j++)f[j]=g[j];
}
for(j=0;j<m;j++)A[j][S]=f[j];
}
for(i=0;i<m;i++)B[i][i]=1;
for(;K;K>>=1,mul(A,A,A))if(K&1)mul(A,B,B);
printf("%d",B[m-1][m-1]);
}
D. Candy Chain
設$f[i][j]$表示將區間$[i,j]$全部消完的最大收益，$dp[i]$表示考慮前$i$個位置的最大收益，那么$dp[i]=\max(dp[i-1],dp[j-1]+f[j][i](1\leq j\leq i))$。
對于$f$的計算，設$g[i][j][k]$表示考慮區間$[i,j]$，最后一次要刪去的串在字典樹上位于$k$點的最大收益，要么枚舉一個區間消掉，要么在字典樹上往下走，要么消去$k$代表的字符串。
時間復雜度$O(n^4c)$，但常數很小，且無用狀態很多，遠遠達不到上界。
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=55,M=20005;
int n,m,i,j,k,x,tot,son[M][26],w[M],f[N][N],dp[N];
int g[N][M];
char a[N],b[N];
inline void up(int&a,int b){a<b?(a=b):0;}
inline void ins(int l,int v){
int x=0;
for(int i=0;i<l;i++){
int o=b[i]-'a';
if(!son[x][o])son[x][o]=++tot;
x=son[x][o];
}
up(w[x],v);
}
int main(){
for(i=1;i<M;i++)w[i]=-1;
scanf("%s",a+1);
n=strlen(a+1);
for(i=1;i<=n;i++)a[i]-='a';
scanf("%d",&m);
while(m--){
int l,w;
scanf("%s%d",b,&w);
l=strlen(b);
ins(l,w);
reverse(b,b+l);
ins(l,w);
}
for(i=0;i<=n+1;i++)for(j=0;j<=n+1;j++)f[i][j]=-1;
for(i=n;i;i--){
for(j=i-1;j<=n+1;j++)for(k=0;k<=tot;k++)g[j][k]=-1;
g[i-1][0]=0;
for(j=i-1;j<=n;j++)for(k=0;k<=tot;k++)if(~g[j][k]){
for(x=j+1;x<=n;x++)if(~f[j+1][x])up(g[x][k],g[j][k]+f[j+1][x]);
if(j<n){
int y=son[k][a[j+1]];
if(y){
up(g[j+1][y],g[j][k]);
if(~w[y])up(g[j+1][0],g[j][k]+w[y]);
}
}
if(k==0)up(f[i][j],g[j][k]);
}
}
for(i=1;i<=n;i++){
dp[i]=dp[i-1];
for(j=1;j<=i;j++)if(~f[j][i])up(dp[i],dp[j-1]+f[j][i]);
}
printf("%d",dp[n]);
}
E. Ingredients
拓撲排序之后背包即可。
#include<stdio.h>
#include<iostream>
#include<string.h>
#include<string>
#include<ctype.h>
#include<math.h>
#include<set>
#include<map>
#include<vector>
#include<queue>
#include<bitset>
#include<algorithm>
#include<time.h>
using namespace std;
void fre() { }
#define MS(x, y) memset(x, y, sizeof(x))
#define ls o<<1
#define rs o<<1|1
typedef long long LL;
typedef unsigned long long UL;
typedef unsigned int UI;
template <class T1, class T2>inline void gmax(T1 &a, T2 b) { if (b > a)a = b; }
template <class T1, class T2>inline void gmin(T1 &a, T2 b) { if (b < a)a = b; }
const int N = 1e6 + 10, M = 0, Z = 1e9 + 7, inf = 0x3f3f3f3f;
template <class T1, class T2>inline void gadd(T1 &a, T2 b) { a = (a + b) % Z; }
int casenum, casei;
int B, n;
char s1[N][24];
char s2[N][24];
char s3[N][24];
int c[N];
int v[N];
int cc[N];
int vv[N];
int ind[N];
int sta[N];
map<string, int>mop;
int ID;
vector< pair<int,int> >a[N];
int getid(char s[24])
{
if(!mop.count(s))
{
mop[s] = ++ID;
a[ID].clear();
cc[ID] = inf;
vv[ID] = -inf;
ind[ID] = 0;
}
return mop[s];
}
bool e[N];
LL f[10005];
int main()
{
while(~scanf("%d%d", &B, &n))
{
ID = 0;
mop.clear();
for(int i = 1; i <= n; ++i)
{
scanf("%s%s%s%d%d", s1[i], s2[i], s3[i], &c[i], &v[i]);
int z = getid(s1[i]);
int x = getid(s2[i]);
int y = getid(s3[i]);
++ind[z];
a[x].push_back({y, i});
a[y].push_back({x, i});
e[i] = 0;
}
int top = 0;
for(int i = 1; i <= ID; ++i)if(ind[i] == 0)
{
sta[++top] = i;
cc[i] = vv[i] = 0;
}
while(top)
{
int x = sta[top--];
for(auto it : a[x])
{
int y = it.first;
int o = it.second;
if(!e[o] && ind[y] == 0)
{
e[o] = 1;
int z = mop[s1[o]];
int cost = cc[x] + cc[y] + c[o];
int val = vv[x] + vv[y] + v[o];
if(cost < cc[z] || cost == cc[z] && val > vv[z])
{
cc[z] = cost;
vv[z] = val;
}
if(--ind[z] == 0)
{
sta[++top] = z;
}
}
}
}
MS(f, -63); f[0] = 0;
for(int i = 1; i <= ID; ++i)
{
//
//printf("cc = %d, vv = %d\n", cc[i], vv[i]);
//
for(int j = B; j >= cc[i]; --j)
{
gmax(f[j], f[j - cc[i]] + vv[i]);
}
}
int cost = 0;
LL val = 0;
for(int i = 1; i <= B; ++i)
{
if(f[i] > val)
{
val = f[i];
cost = i;
}
}
printf("%lld\n%d\n", val, cost);
}
return 0;
}
/*
【trick&&吐槽】
6 2
pizza_tomato pizza_base tomato 1 2
pizza_classic pizza_tomato cheese 5 5
7 2
pizza_tomato pizza_base tomato 1 2
pizza_classic pizza_tomato cheese 5 5
9 2
pizza_tomato pizza_base tomato 1 2
pizza_classic pizza_tomato cheese 5 5
100 2
pizza_tomato pizza_base tomato 1 2
pizza_classic pizza_tomato cheese 5 5
【題意】
【分析】
【時間復雜度&&優化】
*/
F. Shattered Cake
$ans=\frac{\sum_{i=1}^n w_il_i}{W}$。
#include<cstdio>
int w,n;long long s;
int main(){
scanf("%d%d",&w,&n);
while(n--){
int x,y;
scanf("%d%d",&x,&y);
s+=x*y;
}
printf("%lld",s/w);
}
G. Cordon Bleu
考慮費用流建圖，新建一個容量為$n-1$的虛點，表示從餐廳出發的快遞員，剩下部分顯然，然后求最小費用最大流。
這樣邊數為$O(n^2)$，不能接受。注意到這些邊費用都是曼哈頓距離，將絕對值拆開后$4$個象限分別用可持久化線段樹優化建圖即可。
如此一來點數邊數均為$O(n\log n)$，可以通過。
#include<stdio.h>
#include<iostream>
#include<string.h>
#include<string>
#include<ctype.h>
#include<math.h>
#include<set>
#include<map>
#include<vector>
#include<queue>
#include<bitset>
#include<algorithm>
#include<time.h>
using namespace std;
void fre() { }
#define MS(x, y) memset(x, y, sizeof(x))
#define ls o<<1
#define rs o<<1|1
typedef long long LL;
typedef unsigned long long UL;
typedef unsigned int UI;
template <class T1, class T2>inline void gmax(T1 &a, T2 b) { if (b > a)a = b; }
template <class T1, class T2>inline void gmin(T1 &a, T2 b) { if (b < a)a = b; }
const int N = 70000, M = 1e6 + 10, Z = 1e9 + 7, inf = 1e9;
template <class T1, class T2>inline void gadd(T1 &a, T2 b) { a = (a + b) % Z; }
int casenum, casei;
int id, ST, ED;
int first[N];
int w[M], c[M], cap[M], cost[M], nxt[M];
int f[N];
int pe[N];
bool e[N];
int tot;
int FLAG=0;
void ins(int x, int y, int cap_, int cost_)
{
if(!x||!y)return;
if(FLAG)swap(x,y);
id ++;
w[id] = y;
cap[id] = cap_;
cost[id] = cost_;
nxt[id] = first[x];
first[x] = id;
id ++;
w[id] = x;
cap[id] = 0;
cost[id] = -cost_;
nxt[id] = first[y];
first[y] = id;
}
int q[N];
unsigned short head,tail;
void inq(int x, int cost_)
{
if(cost_ >= f[x]) return;
f[x] = cost_;
//pe[x] = pe_;
if(e[x]) return; e[x] = 1;
// if(cost_<q[head])q[--head]=x;else
q[++tail]=x;
}
int vis[N], tim;
int dfs(int x, int all)
{
if(x == ST) return all;
int use = 0;
vis[x] = tim;
for(int z = first[x]; z; z = nxt[z]) if(cap[z ^ 1]){
int y = w[z];
if(vis[y] != tim && f[y] + cost[z ^ 1] == f[x]){
int tmp = dfs(y, min(cap[z ^ 1], all - use));
cap[z ^ 1] -= tmp;
cap[z] += tmp;
use += tmp;
if(use == all) break;
}
}
return use;
}
bool spfa()
{
for(int i=0;i<=tot+10;i++)f[i]=inf;
cap[0] = inf;
head=1,tail=0;
inq(ST, 0);
while(head!=tail+1){
int x = q[head++]; e[x]=0;
for(int z = first[x]; z; z = nxt[z]){
if(cap[z]) inq(w[z], f[x] + cost[z]);
}
}
return f[ED] < inf;
}
int MCMF()
{
int maxflow = 0;
int mincost = 0;
while(spfa()){
int flow;
while(++tim, flow = dfs(ED, inf))
{
maxflow += flow;
mincost += f[ED] * flow;
}
}
//printf("%d\n",maxflow);
return mincost;
}
/*int MCMF()
{
int maxflow = 0;
int mincost = 0;
while(spfa()){
int flow = ~0U>>1;
int x = ED;
while(x != ST){
gmin(flow, cap[pe[x]]);
x = w[pe[x] ^ 1];
}
maxflow += flow;
mincost += f[ED] * flow;
x = ED;
while(x != ST){
cap[pe[x]] -= flow;
cap[pe[x] ^ 1] += flow;
x = w[pe[x] ^ 1];
}
}
return mincost;
//printf("%d %d\n", maxflow, mincost);
}*/
struct point
{
int x, y;
};
int dis(point a, point b)
{
return abs(a.x - b.x) + abs(a.y - b.y);
}
int n, m;
point a, b[N], cc[N];
int ans;
int pool[N];
inline bool cmpx(int x,int y){
return b[x].x<b[y].x;
}
int root0[1111],root1[1111];
int sonl[200000],sonr[200000];
int Ins(int x,int a,int b,int c,int p,int w){
int y=++tot;
if(a==b){
ins(y,x,inf,0);
ins(y,p,inf,w);
return y;
}
int mid=(a+b)>>1;
if(c<=mid){
sonl[y]=Ins(sonl[x],a,mid,c,p,w);
sonr[y]=sonr[x];
}else{
sonl[y]=sonl[x];
sonr[y]=Ins(sonr[x],mid+1,b,c,p,w);
}
ins(y,sonl[y],inf,0);
ins(y,sonr[y],inf,0);
return y;
}
void ask(int x,int a,int b,int c,int d,int p,int w){
if(!x)return;
if(c<=a&&b<=d){
ins(p,x,inf,w);
return;
}
int mid=(a+b)>>1;
if(c<=mid)ask(sonl[x],a,mid,c,d,p,w);
if(d>mid)ask(sonr[x],mid+1,b,c,d,p,w);
}
void solve()
{
MS(first, 0); id = 1;
ED = m + n + 1;
ST = m + n + 4;
int R = m + n + 2;
for(int i = 1; i <= m; i ++)
{
ins(ST, i, 1, 0);
/*for(int j = 1; j <= n; j ++)
{
ins(i, j + m, 1, dis(cc[i], b[j]));
}*/
}
tot=ST;
for(int i=1;i<=n;i++)pool[i]=i;
sort(pool+1,pool+n+1,cmpx);
root0[0]=root1[0]=0;
for(int i=1;i<=n;i++){
int x=pool[i];
root0[i]=Ins(root0[i-1],0,2000,b[x].y,x+m,-b[x].x-b[x].y);
root1[i]=Ins(root1[i-1],0,2000,b[x].y,x+m,-b[x].x+b[x].y);
}
for(int i=1;i<=m;i++){
int j=0;
int X=cc[i].x,Y=cc[i].y;
while(j<n&&b[pool[j+1]].x<=X)j++;
ask(root0[j],0,2000,0,Y,i,X+Y);
ask(root1[j],0,2000,Y,2000,i,X-Y);
}
reverse(pool+1,pool+n+1);
for(int i=1;i<=n;i++){
int x=pool[i];
root0[i]=Ins(root0[i-1],0,2000,b[x].y,x+m,b[x].x-b[x].y);
root1[i]=Ins(root1[i-1],0,2000,b[x].y,x+m,b[x].x+b[x].y);
}
for(int i=1;i<=m;i++){
int j=0;
int X=cc[i].x,Y=cc[i].y;
while(j<n&&b[pool[j+1]].x>=X)j++;
ask(root0[j],0,2000,0,Y,i,-X+Y);
ask(root1[j],0,2000,Y,2000,i,-X-Y);
}
for(int i = 1; i <= n; i ++)
{
ins(R, m + i, 1, dis(a, b[i]));
ins(m + i, ED, 1, 0);
}
ins(ST, R, n - 1 , 0);
//printf("%d %d\n",tot,id);return;
if(FLAG)swap(ST,ED);
ans += MCMF();
printf("%d\n", ans);
}
inline void getnum(int &x){
scanf("%d",&x);
//x=rand()%2001-1000;
x+=1000;
}
int main()
{
scanf("%d%d", &n, &m);//huowu ren
for(int i = 1; i <= n; i ++){
getnum(b[i].x);
getnum(b[i].y);
}
for(int i = 1; i <= m; i ++){
getnum(cc[i].x);
getnum(cc[i].y);
}
getnum(a.x);
getnum(a.y);
ans = 0;
for(int i = 1; i <= n; ++i)
{
ans += dis(a, b[i]);
}
solve();
return 0;
}
/*
【trick&&吐槽】
3 10
0 0
10 0
0 10
【題意】
【分析】
【時間復雜度&&優化】
*/
H. Kabobs
留坑。
I. Burglary
設$f[i][j][k]$表示考慮從上往下前$i$行，目前兩條路線分別位于第$i$行的第$j$和第$k$根管道上的最大收益，暴力轉移即可。
時間復雜度$O(10^4n)$。
#include<stdio.h>
#include<iostream>
#include<string.h>
#include<string>
#include<ctype.h>
#include<math.h>
#include<set>
#include<map>
#include<vector>
#include<queue>
#include<bitset>
#include<algorithm>
#include<time.h>
using namespace std;
void fre() { }
#define MS(x, y) memset(x, y, sizeof(x))
#define ls o<<1
#define rs o<<1|1
typedef long long LL;
typedef unsigned long long UL;
typedef unsigned int UI;
template <class T1, class T2>inline void gmax(T1 &a, T2 b) { if (b > a)a = b; }
template <class T1, class T2>inline void gmin(T1 &a, T2 b) { if (b < a)a = b; }
const int N = 1005, M = 5005, Z = 1e9 + 7, inf = 0x3f3f3f3f;
template <class T1, class T2>inline void gadd(T1 &a, T2 b) { a = (a + b) % Z; }
int casenum, casei;
int n, m;
char s[M];
int gv[N];
int v[N][M];
int p[N][M];
int gt[N];
int t[N][M];
int sum[N][M];
int f[N][12][12];
int main()
{
while (~scanf("%d%d", &n, &m))
{
for (int i = 1; i <= n; ++i)
{
scanf("%s", s + 1);
gv[i] = 0;
p[i][0] = 0;
v[i][0] = 0;
for (int j = 1; j <= m; ++j)if (isdigit(s[j]))
{
v[i][++gv[i]] = s[j] - '0';
p[i][gv[i]] = j;
}
++gv[i];
p[i][gv[i]] = m + 1;
v[i][gv[i]] = 0;
for (int j = 1; j <= gv[i]; ++j)
{
sum[i][j] = sum[i][j - 1] + v[i][j];
}
//
scanf("%s", s + 1);
gt[i] = 0;
for (int j = 1; j <= m; ++j)if (s[j] == '|')
{
t[i][++gt[i]] = j;
}
}
MS(f, -63);
MS(f[1], 0);
for (int o = 1; o < n; ++o)
{
for (int i = 1; i <= gt[o]; ++i)
{
for (int j = i; j <= gt[o]; ++j)if (f[o][i][j] >= 0)
{
for (int ii = 1; ii <= gt[o + 1]; ++ii)
{
for (int jj = ii; jj <= gt[o + 1]; ++jj)
{
int l1 = min(t[o][i], t[o + 1][ii]);
int r1 = max(t[o][i], t[o + 1][ii]);
int l2 = min(t[o][j], t[o + 1][jj]);
int r2 = max(t[o][j], t[o + 1][jj]);
int ll1 = lower_bound(p[o + 1], p[o + 1] + gv[o + 1] + 1, l1) - p[o + 1];
int rr1 = upper_bound(p[o + 1], p[o + 1] + gv[o + 1] + 1, r1) - p[o + 1] - 1;
int ll2 = lower_bound(p[o + 1], p[o + 1] + gv[o + 1] + 1, l2) - p[o + 1];
int rr2 = upper_bound(p[o + 1], p[o + 1] + gv[o + 1] + 1, r2) - p[o + 1] - 1;
//
int ll = max(ll1, ll2);
int rr = min(rr1, rr2);
if (ll <= rr)
{
int inside = sum[o + 1][rr]; if (ll)inside -= sum[o + 1][ll - 1];
if (inside)continue;
}
l1 = upper_bound(p[o + 1], p[o + 1] + gv[o + 1] + 1, l1) - p[o + 1] - 1;
r1 = lower_bound(p[o + 1], p[o + 1] + gv[o + 1] + 1, r1) - p[o + 1];
l2 = upper_bound(p[o + 1], p[o + 1] + gv[o + 1] + 1, l2) - p[o + 1] - 1;
r2 = lower_bound(p[o + 1], p[o + 1] + gv[o + 1] + 1, r2) - p[o + 1];
//
if (l1 > l2)
{
swap(l1, l2);
swap(r1, r2);
}
//one segment
int val;
if (l2 <= r1 + 1)
{
int l = l1;
int r = max(r1, r2);
val = sum[o + 1][r]; if (l)val -= sum[o + 1][l - 1];
}
//two segment
else
{
val = sum[o + 1][r1]; if (l1)val -= sum[o + 1][l1 - 1];
val += sum[o + 1][r2]; if (l2)val -= sum[o + 1][l2 - 1];
}
gmax(f[o + 1][ii][jj], f[o][i][j] + val);
}
}
}
}
}
int ans = 0;
for (int o = 1; o <= n; ++o)
{
for (int i = 1; i <= gt[o]; ++i)
{
for (int j = i; j <= gt[o]; ++j)if (f[o][i][j] >= 0)
{
int l = t[o][i];
int r = t[o][j];
l = upper_bound(p[o + 1], p[o + 1] + gv[o + 1] + 1, l) - p[o + 1] - 1;
r = lower_bound(p[o + 1], p[o + 1] + gv[o + 1] + 1, r) - p[o + 1];
int val = sum[o + 1][r]; if (l)val -= sum[o + 1][l - 1];
gmax(ans, f[o][i][j] + val);
}
}
}
printf("%d\n", ans);
}
return 0;
}
/*
【trick&&吐槽】
【題意】
【分析】
【時間復雜度&&優化】
5 20
--------------------
.|.....|...|......|.
1-1--1115-3-1-1--1-1
....|.........|.....
---1-11-1-11---1--3-
.......|.........|..
-7----9-4-----------
..|.................
--------9-----------
.|.................|
*/
J. Frosting on the Cake
按題意模擬即可。
#include<stdio.h>
#include<iostream>
#include<string.h>
#include<string>
#include<ctype.h>
#include<math.h>
#include<set>
#include<map>
#include<vector>
#include<queue>
#include<bitset>
#include<algorithm>
#include<time.h>
using namespace std;
void fre() { }
#define MS(x, y) memset(x, y, sizeof(x))
#define ls o<<1
#define rs o<<1|1
typedef long long LL;
typedef unsigned long long UL;
typedef unsigned int UI;
template <class T1, class T2>inline void gmax(T1 &a, T2 b) { if (b > a)a = b; }
template <class T1, class T2>inline void gmin(T1 &a, T2 b) { if (b < a)a = b; }
const int N = 0, M = 0, Z = 1e9 + 7, inf = 0x3f3f3f3f;
template <class T1, class T2>inline void gadd(T1 &a, T2 b) { a = (a + b) % Z; }
int casenum, casei;
int n;
LL a[3], b[3], c[3];
int main()
{
while(~scanf("%d",&n))
{
MS(a, 0); MS(b, 0); MS(c, 0);
for(int i = 1; i <= n; ++i)
{
int x; scanf("%d", &x);
a[i % 3] += x;
}
for(int i = 1; i <= n; ++i)
{
int x; scanf("%d", &x);
b[i % 3] += x;
}
for(int i = 0; i < 3; ++i)
{
for(int j = 0; j < 3; ++j)
{
c[(i + j) % 3] += a[i] * b[j];
}
}
printf("%lld %lld %lld\n", c[0], c[1], c[2]);
}
return 0;
}
/*
【trick&&吐槽】
【題意】
【分析】
【時間復雜度&&優化】
*/
K. Blowing Candles
求凸包后旋轉卡殼，注意特判所有點共線的情況。
#include<stdio.h>
#include<iostream>
#include<string.h>
#include<string>
#include<ctype.h>
#include<math.h>
#include<set>
#include<map>
#include<vector>
#include<queue>
#include<bitset>
#include<algorithm>
#include<time.h>
using namespace std;
void fre() { }
#define MS(x, y) memset(x, y, sizeof(x))
#define ls o<<1
#define rs o<<1|1
typedef long long LL;
typedef unsigned long long UL;
typedef unsigned int UI;
template <class T1, class T2>inline void gmax(T1 &a, T2 b) { if (b > a)a = b; }
template <class T1, class T2>inline void gmin(T1 &a, T2 b) { if (b < a)a = b; }
const int N = 2e5 + 10, M = 0, Z = 1e9 + 7, inf = 0x3f3f3f3f;
template <class T1, class T2>inline void gadd(T1 &a, T2 b) { a = (a + b) % Z; }
int casenum, casei;
LL sqr(LL x)
{
return x * x;
}
struct point
{
LL x, y;
point(){}
point(LL x, LL y) : x(x), y(y) {}
friend point operator + (const point &a, const point &b){
return point(a.x + b.x, a.y + b.y);
}
friend point operator - (const point &a, const point &b){
return point(a.x - b.x, a.y - b.y);
}
friend point operator * (const point &a, const double &b){
return point(a.x * b, a.y * b);
}
friend point operator / (const point &a, const double &b){
return point(a.x / b, a.y / b);
}
friend bool operator == (const point &a, const point &b){
return a.x == b.x && a.y == b.y;
}
};
LL det(point a, point b)
{
return a.x * b.y - a.y * b.x;
}
LL dot(point a, point b)
{
return a.x * b.x + a.y * b.y;
}
LL dist(point a, point b)
{
return sqr(a.x - b.x) + sqr(a.y - b.y);
}
struct polygon_convex
{
vector<point> p;
polygon_convex(int size = 0){
p.resize(size);
}
};
bool comp_less(const point &a, const point &b)
{
return a.x - b.x < 0 || a.x - b.x == 0 && a.y - b.y < 0;
}
polygon_convex convex_hull(vector<point> a)
{
polygon_convex res(2 * a.size() + 5);
sort(a.begin(), a.end(), comp_less);
a.erase(unique(a.begin(), a.end()), a.end());
int m = 0;
for(int i = 0; i < a.size(); i ++){
while(m > 1 && det(res.p[m - 1] - res.p[m - 2], a[i] - res.p[m - 2]) <= 0) -- m;
res.p[m ++] = a[i];
}
int k = m;
for(int i = int(a.size()) - 2; i >= 0; i --){
while(m > k && det(res.p[m - 1] - res.p[m - 2], a[i] - res.p[m - 2]) <= 0) -- m;
res.p[m ++] = a[i];
}
res.p.resize(m);
if(a.size() > 1) res.p.resize(m - 1);
return res;
}
LL cross(point a, point b, point c)
{
return (c.x - a.x) * (b.y - a.y) - (b.x - a.x) * (c.y - a.y);
}
int R;
double rotating_calipers(point *p, int n)
{
int U = 1;
double ans = 2.0 * R;
p[n] = p[0];
for(int i = 0; i < n; i ++){
while(cross(p[i], p[i + 1], p[U + 1]) - cross(p[i], p[i + 1], p[U]) <= 0) U = (U + 1) % n;
double d = sqrt(dist(p[i], p[i + 1]));
double h = 1.0 * fabs(cross(p[i], p[i + 1], p[U])) / d;
gmin(ans, h);
}
return ans;
}
int n;
point t, p[N];
polygon_convex a;
int main()
{
scanf("%d%d", &n, &R);
for(int i = 0; i < n; i ++){
scanf("%lld%lld", &t.x, &t.y);
a.p.push_back(t);
}
a = convex_hull(a.p);
n = a.p.size();
for(int i = 0; i < n; i ++){
p[i] = a.p[i];
}
double ans;
if(n <= 2){
printf("0.000000000");
}
else {
ans = rotating_calipers(p, n);
printf("%.10f\n", ans);
}
return 0;
}
/*
【trick&&吐槽】
3 10
0 0
10 0
0 10
【題意】
【分析】
【時間復雜度&&優化】
*/
浙公網安備 33010602011771號