【NOIP模拟赛】小奇颓废赛 Day1

D1T1

问题 A: 小奇挖矿

【题目背景】
小奇要开采一些矿物，它驾驶着一台带有钻头（初始能力值w）的飞船，按既定路线依次飞过喵星系的n个星球。
【问题描述】
星球分为2类：资源型和维修型。 
1.资源型：含矿物质量a[i]，若选择开采，则得到a[i]*p的金钱，之后钻头损耗k%，即p=p*(1-0.01k)
2.维修型：维护费用b[i]，若选择维修，则支付b[i]*p的金钱，之后钻头修复c%，即p=p*(1+0.01c)（p为钻头当前能力值）
注：维修后钻头的能力值可以超过初始值
请你帮它决策最大化这个收入

输入
第一行4个整数n，k，c，w。
以下n行，每行2个整数type，x。
type为1则代表其为资源型星球，x为其矿物质含量a[i]；
type为2则代表其为维修型星球，x为其维护费用b[i]；

输出
输出一行一个实数（保留两位小数），表示要求的结果。

样例输入
5 50 50 10
1 10
1 20
2 10
2 20
1 30

样例输出
375.00

提示
对于30%的数据 n<=100
对于50%的数据 n<=1000，k=100
对于100%的数据 n<=100000，0<=k，c，w，a[i]，b[i]<=100
保证答案不超过10^9

初眼思路：记忆化搜索

然而好像运行错误，我也不知道为什么

正解：线性动态规划

• 因为得到的钱或者支付的钱与当前能力成正比，所以我们可以设一个数组来存当前的能力和钱的混合值

• 因为具有前效性，所以要倒着推虽然我也不知道为什么

核心代码

for(int i=n;i>=1;i--) {
        if(s[i][0]==1) f[i-1]=max(f[i],f[i]*(1-0.01*k)+a[i]*w);
        else f[i-1]=max(f[i],f[i]*(1+0.01*c)-b[i]*w);
    }

---

D1T2

问题 B: 小奇的数列

【题目背景】
小奇总是在数学课上思考奇怪的问题。
 【问题描述】
给定一个长度为n的数列，以及m次询问，每次给出三个数l，r和P，询问 (a[l'] + a[l'+1] + ... + a[r']) mod P的最小值。
其中l <= l' <= r' <= r。 
即模意义下的区间子串和最小值。

输入
第一行包含两个正整数n和m，表示数列的长度和询问的个数。
第二行为n个整数，为a[1]..a[n]。
接下来m行，每行三个数l，r和P，代表一次询问。

输出
对于每次询问，输出一行一个整数表示要求的结果

样例输入
4 2
8 15 9 9
1 3 10
1 4 17

样例输出
2
1

提示
对于20%的数据 n<=100，m<=100，p<=200
对于40%的数据 n<=200，m<=1000，p<=500
对于70%的数据 n<=100000，m<=10000，p<=200
对于100%的数据 n<=500000，m<=10000，p<=500，1<=a[i]<=10^9

初眼思路：暴力

• 开一个数组记录前缀和，枚举所有区间 50pts

暴力优化

• 一旦发现当前值为0，可以直接break 90pts
• 还可以开一个桶，具体做法我也不太清楚，但是可以AC，跑的还比正解快多了暴力大法好

正解：平衡树

• 仍然开一个数组记录前缀和，每次都检索当前前驱寻找最小差值，然后插入平衡树，记得每次都要初始化

AC代码

#include<cstdio>
#include<algorithm>
#include<cstring>
#define SI 500010
#define inf 0x3f3f3f3f
using namespace std;
struct treap {
	int l,r,dat,val;
}a[1010];
int n,m,rt,mn,tot,t[SI];
long long s[SI];
inline int New(int val) {
	a[++tot].val=val;
	a[tot].dat=rand();
	return tot;
}
inline void zig(int &p) {//右旋 
	int q=a[p].l;
	a[p].l=a[q].r,a[q].r=p,p=q;
}
inline void zag(int &p) {//左旋 
	int q=a[p].r;
	a[p].r=a[q].l,a[q].l=p,p=q;
}
inline void insert(int &p,int val) {
	if(p==0) {
		p=New(val);
		return;
	}
	if(val==a[p].val) return;
	if(val<a[p].val) {
		insert(a[p].l,val);
		if(a[p].dat<a[a[p].l].dat) zig(p);
	}
	else {
		insert(a[p].r,val);
		if(a[p].dat<a[a[p].r].dat) zag(p);
	}
}
inline void Remove(int &p,int val) {
	if(p==0) return;
	if(val==a[p].val) {
		mn=0;
		return;
	}
	if(val<a[p].val) Remove(a[p].l,val);
	else {
		mn=min(mn,val-a[p].val);
		Remove(a[p].r,val);
	}
}
int main() {
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++) {
		scanf("%d",&t[i]);
		s[i]=s[i-1]+t[i];
	}
	while(m--) {
		memset(a,0,sizeof(a));
		int l,r,p;
		scanf("%d%d%d",&l,&r,&p);
		int ans=p;
		if(r-l+1>=p) {
			printf("0\n");
			continue;
		}
		rt=tot=0; insert(rt,0);
		for(int j=l;j<=r;j++) {
			int tmp=(s[j]-s[l-1])%p;
			mn=inf; Remove(rt,tmp);
			insert(rt,tmp);
			ans=min(ans,mn);
			if(!ans) break;
		}
		printf("%d\n",ans);
	}
	return 0;
}

---

D1T3

小奇回地球

【题目背景】
开学了，小奇在回地球的路上，遇到了一个棘手的问题。
 【问题描述】
简单来说，它要从标号为1的星球到标号为n的星球，某一些星球之间有航线。
由于超时空隧道的存在，从一个星球到另一个星球时间可能会倒流，而且，从星球a到b耗费的时间和星球b到a耗费的时间不一定相同。
 宇宙法规定：“禁止在出发时间前到达目的地。”
每艘飞船上都有速度调节装置，可以调节飞行的时间。其功能可以使得整次航程中所有两星球间的飞行时间增加或减少相同的整数值。
你的任务是帮助它调整速度调节器，找出一条最短时间到达目的地的路径。

输入
输入文件包含多组数据，第1个数为T，表示数据组数。
对于每组数据，输入第1行为两个正整数n，m，为星球的个数和星球间的路线数。
接下来m行，每行三个整数i，j和t，表示由星球i到星球j飞行的时间为t。由i到j最多只会有一条飞行线路。

输出
输出文件共T行，每组数据输出一行。
如果可以通过调节速度调节器完成任务，则输出一个非负整数，表示由星球1到星球n的最短时间。（注意最短时间要大于或者等于0）。
如果不能由星球1到达星球n，则输出-1。

样例输入
1
4 5
1 2 1
1 3 1
2 3 -3
3 1 1
3 4 1

样例输出
2

提示
【样例解释】
把速度控制器的值设为1,相当于每个时间值加1,得到的最短路径为1→2→3→4,所需时间为2+(-2)+2=2。
 
【数据范围】
1，2号测试点，保证所有星球出度不超过1
3，4号测试点，n<=10
5，6号测试点，-100<=t<=100
对于100%的数据T<=10，n<=100，m<=n*(n-1)，-100000<=t<=100000
数据随机和构造结合生成

初眼思路：图上二分

正解：图上二分

真·D1唯一真正会做的题

• 首先最重要的一点，多组数据记得初始化，不要以为memset就完事了，还有你建边用的cnt别忘了归零，我就这样运行错误了两次

• 需要判断负环，我们可以用SPFA来判断更迭次数，当更迭次数大于n时就知道有负环，我们可以加大时间

• 在SPFA中我们还需要判断中转点是否可以到目的地，我用的是floyed算法，开一个布尔数组来记录两点之间是否联通

• 二分别打错了

AC代码

#include<cstdio>
#include<queue>
#include<cstring>
#define inf 0x3f3f3f3f
using namespace std;
struct edge {
    int nex,to,w;
}e[10010];
int T,n,m,cnt,ans,head[105],dis[105],Cnt[105];
bool vis[105][105],v[105]; queue<int> q;
inline int read() {
    int c=getchar(),x=0,cf=1;
    while(c<'0'||c>'9') {
        if(c=='-') cf=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9') {
        x=x*10+c-'0';
        c=getchar();
    }
    return x*cf;
}
inline void add(int x,int y,int z) {
    e[++cnt].to=y,e[cnt].w=z,e[cnt].nex=head[x],head[x]=cnt;
}
inline bool spfa(int s,int d) {
    memset(dis,0x3f,sizeof(dis));
    memset(v,false,sizeof(v));
    memset(Cnt,0,sizeof(Cnt));
    dis[s]=0,v[s]=1,Cnt[s]=0;
    q.push(s);
    while(q.size()) {
        int x=q.front(); q.pop(); v[x]=0;
        if(Cnt[x]>=n) return true;
        for(int i=head[x];i;i=e[i].nex) {
            int y=e[i].to,z=e[i].w;
            if(dis[y]>dis[x]+z+d&&vis[y][n]) {
                dis[y]=dis[x]+z+d;
                Cnt[y]=Cnt[x]+1;
                if(Cnt[y]>=n) return true;
                if(!v[y]) q.push(y),v[y]=1;
            }
        }
    }
    if(dis[n]<0||dis[n]==inf) return true;
    return false;
}
int main() {
    T=read();
    while(T--) {
        memset(head,0,sizeof(head));
        memset(e,0,sizeof(e));
        memset(vis,false,sizeof(vis));
        n=read(),m=read(); cnt=0;
        for(int i=1;i<=m;i++) {
            int x,y,z;
            x=read(),y=read(),z=read();
            add(x,y,z); vis[x][y]=true;
        }
        for(int i=1;i<=n;i++) vis[i][i]=true;
        for(int k=1;k<=n;k++)
            for(int i=1;i<=n;i++)
                for(int j=1;j<=n;j++)
                    if(vis[i][k]&&vis[k][j]) vis[i][j]=true;
        if(!vis[1][n]) {
            printf("-1\n");
            continue;
        }
        int l=-100000,r=100000;
        ans=-1;
        while(l<=r) {
            int mid=(l+r)>>1;
            if(spfa(1,mid)) l=mid+1;
            else r=mid-1,ans=dis[n];
        }
        printf("%d\n",ans);
    }
    return 0;
}

最终得分100+90+0=190，还需要继续努力啊