P4013 数字梯形问题
题目描述
给定一个由 nn 行数字组成的数字梯形如下图所示。
梯形的第一行有 m 个数字。从梯形的顶部的 m 个数字开始，在每个数字处可以沿左下或右下方向移动，形成一条从梯形的顶至底的路径。
分别遵守以下规则：
从梯形的顶至底的 m 条路径互不相交；
从梯形的顶至底的 m 条路径仅在数字结点处相交；
从梯形的顶至底的 m 条路径允许在数字结点相交或边相交。
输入输出格式
输入格式：
第 1 行中有 2 个正整数 m 和 n ，分别表示数字梯形的第一行有 m 个数字，共有 n 行。接下来的 n 行是数字梯形中各行的数字。
第 1 行有 m 个数字，第 2 行有 m+1 个数字，以此类推。
输出格式：
将按照规则 1 ，规则 2 ，和规则 3 计算出的最大数字总和并输出，每行一个最大总和。
输入输出样例
输入样例#1：
2 5
2 3
3 4 5
9 10 9 1
1 1 10 1 1
1 1 10 12 1 1
输出样例#1：
66
75
77
说明
(1leq m,n leq 20)
7.19考试T3
LMC刚说了网络流字符串只会板子就行然后就考了网络流
s和t就不说了
规则1：
点和边都不能相交
边不能相交，我们可以把流量设为1
点的话，网络流最常用的方法就是拆点
点1连接入边，点2连接出边，然后点1和点2连接起来，流量为1
规则2：
点随便走的话，就不用管它了
边的流量为1
注意，最后一层向t连边的时候是inf
（一个1 AC变暴力考试细节爆炸）
规则三：
数字三角形
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <cstring>
#define maxn 50007
using namespace std;
int a[maxn];
int belong[maxn];
int vis[maxn];
int ans[maxn];
int n,m,k;
int mi,ma;
inline int read()
{
int x=0,f=1;char s=getchar();
while('0'>s||s>'9') {if(s=='-')f=-1;s=getchar();}
while('0'<=s&&s<='9') {x=x*10+s-'0';s=getchar();}
return x*f;
}
struct node{
int x,y,id,mod;
}q[maxn];
inline bool cmp(const node &a,const node &b) {
belong[a.x]==belong[b.x] ? a.y<b.y :a.x<b.x;
}
int gcd(int a,int b) {
return !b?a:gcd(b,a%b);
}
int main()
{
n=read();
m=read();
int k=sqrt(n);
for(int i=1;i<=n;++i)
belong[i]=(i-1)/k+1;
mi=0x3f3f3f3f;
ma=-mi;
for(int i=1;i<=n;++i)
{
a[i]=read();
mi=min(mi,a[i]);
ma=max(ma,a[i]);
}
for(int i=1;i<=m;++i)
{
q[i].x=read();
q[i].y=read();
q[i].mod=read();
q[i].id=i;
}
sort(q+1,q+1+m,cmp);
int l=0,r=0;
for(int i=1;i<=m;++i)
{
while(l > q[i].x) ++vis[a[--l]];
while(l < q[i].x) --vis[a[l++]];
while(r > q[i].y) --vis[a[r--]];
while(r < q[i].y) ++vis[a[++r]];
int now=0;
for(int j=mi;j<=ma;++j)
{
if(!vis[j]) continue
if(gcd(min(vis[j],q[i].mod),max(vis[j],q[i].mod))==1) now++;
}
ans[q[i].id].ans=now;
}
for(int i=1;i<=m;++i)
printf("%d
",ans[i]);
return 0;
}