题目描述
输入
第一行是5个正整数，n，m，k，S，T，分别代表无向图点数，边数，蝙蝠的数量，二小姐所在起点的编号，目标点的编号。
第二行是k个正整数，分别代表大小姐每个蝙蝠所在的起点的编号。接下来有m行，每行有4个正整数，u，v，q，p，分别是该边的起点、终点，蝙蝠通过该
路花费的代价，二小姐通过该路花费的代价。
输出
一行，一个整数，所有人物达到终点所需要的代价的和的最小值。
样例输入
5 5 2 3 4 1 5 1 2 3 5 3 2 3 5 2 4 4 9 3 4 9 6 5 4 1 1
样例输出
13
提示
1号蝙蝠从1到2，花费3
二小姐从3到2，花费5，遇见蝙蝠，之后不计算费用1号蝙蝠从2到4，花费4
2号蝙蝠从5到4，花费1
总计13
其中30%：n<=200。另有20%:保证S=T。
另有20%：保证k<=5，n<=1000,m<=10000。100%：n<=10000，m<=100000，k<=10000，1<=S、T、u、v<=n，1<=p、q<=1000，不保证
蝙蝠起点互不相等，数据中可能有重边和自环，保证所有点均能走到T点（即不存在无解情况）。
题解：
很容易想到枚举每一个个点作为蝙蝠和二小姐的交点
但是时间内存不允许，于是我们优化，我们可以虚拟一个S' S'到每一个蝙蝠的起点有一条，长度为 -dist ki-T
然后答案就是sum(F[ki][T])+min(F[s'][i]+F[S][i]+F[i][T])
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=,M=,INF=,MOD=;
int head[N],num=;
struct Lin{
int next,to,dis[];
}a[M<<];
void init(int x,int y,int z1,int z2){
a[++num].next=head[x];a[num].to=y;a[num].dis[]=z1;a[num].dis[]=z2;head[x]=num;
if(!x)return ;a[++num].next=head[y];a[num].to=x;a[num].dis[]=z1;a[num].dis[]=z2;head[y]=num;
}
int gi(){
int str=;char ch=getchar();
while(ch>'' || ch<'')ch=getchar();
while(ch>='' && ch<='')str=str*+ch-,ch=getchar();
return str;
}
int n,m,k,S,T;int f[][N],q[N*],s[N];bool vis[N];
void spfa(int sta,bool tt)
{
for(int i=;i<=n;i++)vis[i]=false,f[sta][i]=INF;
int t=,sum=,x,u;
int from=;
if(sta==)from=S;if(sta==)from=T;if(sta==)from=;
q[]=from;vis[from]=true;f[sta][from]=;
while(t!=sum)
{
t++;t%=MOD;
x=q[t];
for(int i=head[x];i;i=a[i].next)
{
u=a[i].to;
if(a[i].dis[tt]+f[sta][x]<f[sta][u])
{
f[sta][u]=f[sta][x]+a[i].dis[tt];
if(!vis[u])vis[u]=true,sum++,sum%=MOD,q[sum]=u;
}
}
vis[x]=false;
}
}
int main()
{
n=gi();m=gi();k=gi();S=gi();T=gi();
for(int i=;i<=k;i++)s[i]=gi();
int x,y,z1,z2;
for(int i=;i<=m;i++)
{
x=gi();y=gi();z1=gi();z2=gi();
if(x==y)continue;
init(x,y,z1,z2);
}
spfa(,);spfa(,);
long long sum=;
for(int i=;i<=k;i++)init(,s[i],-f[][s[i]],),sum+=f[][s[i]];
spfa(,);
long long ans=INF,tmp;
long long pp=;
for(int i=;i<=n;i++)
{
tmp=f[][i]+f[][i]+f[][i];
if(tmp<ans)ans=tmp,pp=i;
}
printf("%lld",ans+sum);
return ;
}
题目描述
输入
第一行是一个正整数n,表示上式中的p的个数。
接下来有n行,每一行两个正整数pi 和ei 。
输出
样例输入
2 2 2 3 2
样例输出
2 2 3 1
提示
样例解释
N=2*2*3*3=36
phi(N）=36*(1-1/2)*(1-1/3)=12 12=2*2*3
样例输入二
4
37 1
3 4
37 1
333667 2
样例输出二
2 4
3 8
37 2
167 1 333667 1
题解：
水的数论，分解每一个pi-1即可
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
typedef long long ll;
const int N=,M=,T=;
int gi(){
int str=;char ch=getchar();
while(ch>'' || ch<'')ch=getchar();
while(ch>='' && ch<='')str=str*+ch-'',ch=getchar();
return str;
}
bool d[M];int mark[T];bool cf[T];
ll qm(ll x,int k)
{
if(x==)return ;
if(k==)return ;
ll sum=;
while(k)
{
if(k&)sum*=x;
k>>=;x*=x;
}
return sum;
}
int a[T],num=;int z[N],t=;
void qd(int p)
{
int lim;int c;
num=;
for(int i=;i<=t;i++){if(p%z[i]==)a[++num]=z[i];}
for(int i=;i<=num;i++)
{
int k=,tmp=p;
while(tmp)
{
if(tmp%a[i])break;
k++;tmp/=a[i];
}
mark[a[i]]+=k;
}
}
int main()
{
//freopen("pp.in","r",stdin);
int n,x,y;
scanf("%d",&n);
memset(mark,,sizeof(mark));
for(int i=;i<=n;i++)
{
x=gi();y=gi();
mark[x]+=y;
cf[x]=true;
}
int m=1e6;
d[]=false;
for(int i=;i<=m;i++)
{
if(d[i])continue;
z[++t]=i;
for(int j=*i;j<=m;j+=i)d[j]=true;
}
int to=1e6;
for(int i=;i<=to;i++)
{
if(cf[i])
qd(i-),mark[i]--;
}
for(int i=;i<=to;i++)
{
if(mark[i])printf("%d %d\n",i,mark[i]);
}
return ;
}
题目描述
输入
第一行一个正整数n，代表积木的个数。 接下来有n行，每行两个数li，ri，分别代表第i块积木左端点和右端点。
输出
输出一行两个整数，用一个空格隔开，分别代表最底层最多有多少积木和积木最少有多 少层。
样例输入
6 1 2 2 3 4 5 5 6 1 4 3 6
样例输出
4 2
提示
第 1、2、3、4 块放在最底层，第 5 块第二层，第 6块第三层。此时底层共 4块积木。
第 1、2、6块放在最底层，第 3、4、5块第二层。此时高度为 2。
30%：n<=10,0<=l,r<=20
另 20%: n<=100,0<=l<=50,r=l+2,即每块积木长均为 2
100%：n<=100000,-2*10^8<=l,r<=2*10^8
题解：
贪心，第一问线段覆盖，按右端点排序，然后以此判断 l>=last 满足就加入
第二问将每一条线段拆成两个点 再将每个点排序，线性扫描一边，遇l h++遇r h-- 意为能塞入底层就塞入
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=;
int gi(){
int str=,f=;char ch=getchar();
while(ch>'' || ch<''){if(ch=='-')f=-;ch=getchar();}
while(ch>='' && ch<='')str=str*+ch-,ch=getchar();
return str*f;
}
struct Point{
int l,r;
}a[N];
bool comp(const Point &p,const Point &q){return p.r<q.r;}
struct Pointed{
int x;bool t;
}p[N<<];
bool cmp(const Pointed &p,const Pointed &q){if(p.x!=q.x)return p.x<q.x;return p.t>q.t;}
int main()
{
int n=gi();
for(int i=;i<=n;i++)
{
a[i].l=gi();a[i].r=gi();
p[(i<<)-].x=a[i].l;p[(i<<)-].t=;
p[i<<].x=a[i].r;p[i<<].t=;
}
sort(a+,a+n+,comp);
int from=-2e9,ans1=;
for(int i=;i<=n;i++)
{
if(a[i].l>=from)
{
ans1++;
from=a[i].r;
}
}
printf("%d ",ans1);
sort(p+,p+(n<<)+,cmp);
int top=,ans2=,ppap=(n<<);
for(int i=;i<=ppap;i++)
{
if(!p[i].t)top++;
else top--;
if(top>ans2)ans2=top;
}
printf("%d",ans2);
return ;
}
题目描述
擦弹(graze)
输入
第一行是1个正整数n，代表道路长度。
接下来有4n-4行，每行n个整数，第i行第j个数代表在i时刻（开始为0时刻）在第j格内受到的伤害。
输出
两个整数，用空格隔开，分别代表最小的miss数，和在miss数最小的情况下最大的graze 数。
样例输入
2 1 2 2 2 3 2 4 2
样例输出
30 10
提示
只有一种走法。
第一回合：第一格3分身，第二格1分身，miss5，graze1。
第二回合：第一格2分身，第二格2分身，miss8，graze2。
第三回合：第一格1分身，第二格3分身，miss9，graze3。
第四回合：第一格0分身，第二格4分身，miss8，graze4。
其中30%数据:n<=3其中50%数据:n<=10其中70%数据:n<=30
100%数据:n<=100,每时刻每格中弹幕数均为正数且小于 1000
题解：
简单的高维dp 注意高维常数 F[i][j][k][g]表示i时刻，第一个分身走的步数为j，第二个为k，第三个为g，第四个为l-i-j-k的最小miss值
然后以miss为最高优先级，每一次miss更新 graze就更新，miss相等则取较大者
第一维明显可以滚动掉 注意边界条件
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
const int N=,M=;
int F[][N][N][N],p[][N][N][N];int a[N];
int gi(){
int str=;char ch=getchar();
while(ch>'' || ch<'')ch=getchar();
while(ch>='' && ch<='')str=str*+ch-,ch=getchar();
return str;
}
int main()
{
int n;
scanf("%d",&n);
int m=*n-;
int tmp=,l=,pc=;
memset(F,/,sizeof(F));
F[][][][]=;
int c=,cc=;
for(int i=;i<=m;i++)
{
for(int j=;j<=n;j++)
{
a[j]=gi();
}
for(int j=;j<n;j++)
{
if(j>i)break;
for(int k=j;k<n;k++)
{
if(k+j>i)break;
pc=k>i-j-k-n?k:i-j-k-n;
for(int g=pc;g<n;g++)
{
if(g+j+k>i)break;
l=i-j-k-g;
if(l<g-)break;
int *pp=&F[cc][j][k][g];
int *qq=&p[cc][j][k][g];
*pp=2e8;
*qq=;
tmp=a[j+]+a[k+]+a[g+]+a[l+];
if(tmp+F[c][j-][k][g]<=*pp&& j)
{
int t=F[c][j-][k][g];
if(tmp+t<*pp)
*qq=p[c][j-][k][g]+a[j];
else if(p[c][j-][k][g]+a[j]>*qq)*qq=p[c][j-][k][g]+a[j];
*pp=tmp+t;
}
if(tmp+F[c][j][k-][g]<=*pp&& k)
{
int t=F[c][j][k-][g];
if(tmp+t<*pp)
*qq=p[c][j][k-][g]+a[k];
else if(p[c][j][k-][g]+a[k]>*qq)*qq=p[c][j][k-][g]+a[k];
*pp=tmp+t;
}
if(tmp+F[c][j][k][g-]<=*pp&& g)
{
int t=F[c][j][k][g-];
if(tmp+t<*pp)
*qq=p[c][j][k][g-]+a[g];
else if(p[c][j][k][g-]+a[j]>*qq)*qq=p[c][j][k][g-]+a[g];
*pp=tmp+t;
}
if(tmp+F[c][j][k][g]<=*pp)
{
int t=F[c][j][k][g];
if(tmp+t<*pp)
*qq=p[c][j][k][g]+a[l];
else if(p[c][j][k][g]+a[l]>*qq)*qq=p[c][j][k][g]+a[l];
*pp=tmp+t;
}
}
}
}
c^=;cc^=;
}
cout<<F[c][n-][n-][n-]<<" "<<p[c][n-][n-][n-];
return ;
}