2017NOIPDay1(小凯的疑惑 &时间复杂度&逛公园)

目录

• P3951 小凯的疑惑 / [蓝桥杯2013省]买不到的数目
  • 题意
  • 思路
  • 代码（根号下min(a,b)复杂度，可通过）
• P3952 时间复杂度
  • 题意
  • 思路
  • 代码
• P3953 逛公园
  • 题意
  • 思路
    • 输出-1的情况
    • 1版（3TLE）
    • 2版（AC）
    • 疑惑
  • 代码
    • 1版
    • 2版

P3951 小凯的疑惑 / [蓝桥杯2013省]买不到的数目

题意

给两个互质的整数a,b求一个数ans，使得

[∀i > ans , i = x cdot a + y cdot b (a,bin Z) ]

思路

别人的思路：不太清楚别人是怎么搞的，其实就一条式子：ans = (a-1)*b-a;

我的思路（比较复杂）：

首先，强行令a<b

以7,3为例，下面能直接用3表示的画〇，用7，3组合或直接用7表示的画√

0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
〇			〇			〇	√		〇	√		〇	√	√	〇

以3*floor(7/3)=6为一个单位，拆开得：

0	1	2	3	4	5
〇			〇

6	7	8	9	10	11
〇	√		〇	√

12	13	14	15	16	17
〇	√	√	〇	√	√

可以发现，表中是有规律变化的，每一次变化表中都多一个√，我们把上面无限延伸的表抽象成长度为a的表，每一个√的位置就是上一个√位置+b%a(溢出则对a取模)，那么最后一个被填的位置减去a就是答案

还是以7，3为例

x*a	x*a+1	x*a+2
〇

一次变化(x+=floor(b/a))：

x*a	x*a+1	x*a+2
〇	√	(ans)

二次变化(x+=floor(b/a))：

x*a	x*a+1	x*a+2
〇	√	√

显然，再下一次变化后〇和√就重合了(若a,b不互质，则在重合的时候没有完全覆盖，因此永远没有答案)

因此，原问题转化为找

[xcdot a=bcdot y + b \% a(x,yin )……① ]

并使得方程两边的值最小，答案就是

[ax-a-b\%a ]

又因为

[b=acdot floor(b/a)+b\%a ]

①式化为

[xcdot a=ycdot acdot floor(b/a)+(y+1)(b\%a) ]

即使得方程右边是a的倍数，显然,加号左边是a的倍数，那么，就是要让加号右边也是a的倍数，又因为要满足最小，我们对a和b%a分解质因数，如果是a有而b%a无的质因子，我们就用(y+1)补上，使得(y+1)(b%a)是a得倍数

这样y就出来了，答案也自然出来了

代码（根号下min(a,b)复杂度，可通过）

#include <iostream>
#define ll long long
using namespace std;
ll a , b;
int gcd(int a , int b){
	return b == 0 ? a : gcd(b , a % b);
}
int main(){
	cin >> a >> b;
	if(a > b){ll tmp = a ; a = b ; b = tmp;}
	if(a == 1){
		cout << 0;
		return 0;
	}
	ll c = b % a;
	ll d = b / a;
	
	ll tmpa = a , tmpc = c;
	ll y = 1;
	for(ll i = 2 ; i * i <= tmpa ; i++){
		while(tmpa % i == 0){
			if(tmpc % i != 0)
				y *= i;
			else
				tmpc /= i;
			tmpa /= i;
		}
	}
	if(tmpc % tmpa != 0)
		y *= tmpa;
	y--;
	
	ll ax = c + c * y + y * a * d;
	cout << ax - a - c;
	return 0;
} 

P3952 时间复杂度

题意

给一段“A++”代码，算时间复杂度

思路

这种题往往看着简单，实际暗含无数细节

仔细看题，循环范围一共有一下情况：

x	y	对时间复杂度的影响
常数	常数	1.x<=y：常数复杂度 2.x > y：被嵌套的代码不运行
常数	n	n
n	n	常数
n	常数	被嵌套的代码不运行

ERR的情况：

1. F，E不匹配：类似于括号匹配问题,定义变量check=0，遇到F加一，遇到E减一，中途不能小于0，结束时一定为0
2. 变量名不重复：用栈存储即可

几个细节：

1. 递归到什么时候结束：记录总行数，若当前行>m，立刻在输入前退出递归，防止输入错位
2. 循环体的从属问题：将递归函数定义为bool类型，返回true则表示遇到E，当前循环结束

代码

#include <iostream>
#include <cstdio>
#include <string>
using namespace std;
int maxn;
int m;
int stoint(string s){
	int x = 0;
	for(int i = 0 ; i < s.size() ; i++)
		x = (x << 1) + (x << 3) + s[i] - '0';
	return x;
}
int times;
bool err;
string stac[110];
int top;
int check;
bool dfs(int cnt){
	times++;
	if(times > m){
		err = true;
		return true;
	}
	if(cnt > maxn)
		maxn = cnt;
	string x , y , tmp;
	cin >> tmp;
	if(tmp == "E"){
		check--;
		if(check < 0)err = true;
		return true;
	}
	else{
		
		check++;
		cin >> tmp;
//		if(tmp == "m")
//			cout << cnt << "!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
";
		for(int i = 1 ; i <= top ; i++)
			if(tmp == stac[i])
				err = true;
		top++;
		stac[top] = tmp;
		cin >> x >> y;
//		cout << x << endl << y << endl;
		if(x[0] == 'n'){
			if(y[0] == 'n')
				while(!dfs(cnt));
			else
				while(!dfs(-(1 << 29)));
		}
		else{
			if(y[0] == 'n')
				while(!dfs(cnt + 1));
			else{
				if(stoint(x) > stoint(y))
					while(!dfs(-(1 << 29)));
				else
					while(!dfs(cnt));
			}
		}
		top--;
	}
	return false;
} 
int main() {
	int T;
	cin >> T;
	while(T--){
		times = 0;
		maxn = 0;
		err = false;
		top = 0;
		check = 0;
		
		string s;
		cin >> m;
		cin >> s;
		s = s.substr(2 , s.size() - 2 - 1);
//		cout << s << endl;
		int dl = 0;
		if(s[0] != 'n')dl = 0;
		else{
			s = s.substr(2);
			for(int i = 0 ; i < s.size() ; i++)
				dl = dl * 10 + s[i] - '0';
		}
		while(times < m)dfs(0);
		
		if(check != 0)err = true;
		
		if(err)	printf("ERR
");
		else {
			if(maxn == dl)printf("Yes
");
			else	printf("No
");
		}
//		cout << maxn << endl;
//		system("pause");
	}
	return 0;
}

P3953 逛公园

题意

求从1到n的路径数量，满足长度在[dis(1,n) , dis(1,n)+k]范围内(dist(1,n)表示1到n的最短路径长度)

思路

记忆化搜索

看到k才去到50，那么我们就直接在合法范围内枚举路径的长度

输出-1的情况

就是某条路径中包含一个权值为0的环的情况(因为一直绕着环走，路径长度不变，但每次都是不一样的)

1版（3TLE）

定义dfs(x,dist),返回以x为终点，1为起点，长度为dist的路径数量

用map容器记录dfs(x,dist)的值

加点小剪枝：dist<（1到x的最短路径）时，没有方案(return 0)

2版（AC）

参考了这个大佬的博客

dfs(x,dist)表示以x为终点,还差dist长度到达目标路径长度

记忆化直接用数组rec[n] [55]实现即可

转移：

[dfs(x,dist)=Sigma dfs(s,dist - ed2[i].len + (dis[x] - dis[ed2[i].u])) ]

说明：s表示与x相连的点（边从s指向x，这就是开两个链式前向星的原因），ed2[i].u表示上述边的长度，dis[ ]为1到所有点的最短路长度

疑惑

按n=100000,m=200000开数组不够用，会越界，甚至两倍都不行（这就是苦苦调试了很久，改了很多不必改的东西的原因），最后开了10倍才AC

代码

1版

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <map>
#include <set>
#define ll long long
#define nn 1000010
using namespace std;
int read(){
	int re = 0 , sig = 1;
	char c = getchar();
	while(c < '0' || c > '9'){
		if(c == '-')sig = -1;
		c = getchar();
	}
	while(c >= '0' && c <= '9'){
		re = (re << 1) + (re << 3) + c - '0';
		c = getchar();
	}
	return re * sig;
}

struct ednode{
	int u , nxt , len;
}ed[nn * 2] , ed2[nn * 2];
int head[nn] , head2[nn];
inline void addedge(int u , int v , int len){
	static int top = 1;
	if(u == v && u == -1){top = 1;	return;}
	ed[top].u = v , ed[top].len = len , ed[top].nxt = head[u] , head[u] = top;
	top++;
}
inline void addedge2(int u , int v , int len){
	static int top = 1;
	if(u == v && u == -1){top = 1;	return;}
	ed2[top].u = v , ed2[top].len = len , ed2[top].nxt = head2[u] , head2[u] = top;
	top++;
}
int n , m , k ;
ll p;
int dis[nn] ;
ll cnt[nn];
bool vis[nn];
void spfa(){
	memset(dis , 0x3f , sizeof(dis));
	memset(vis , 0 , sizeof(vis));
	memset(cnt , 0 , sizeof(cnt));
	
	queue <int> q;
	dis[1] = 0;
	vis[1] = true;
	cnt[1] = 1;
	q.push(1);
	while(!q.empty()){
		int k = q.front();
		q.pop();
		vis[k] = false;
		for(int i = head[k] ; i ; i = ed[i].nxt){
			if(dis[ed[i].u] > dis[k] + ed[i].len){
				dis[ed[i].u] = dis[k] + ed[i].len;
				cnt[ed[i].u] = 0;
				if(!vis[ed[i].u]){
					q.push(ed[i].u);
					vis[ed[i].u] = true;
				}
			}
		}
	}
}
ll sum;
int goa[nn];
bool break_;
map<pair<int , int> , int> rec;
ll dfs(int x , int dist) {
	if(dist < 0)return 0;
	if(goa[x] == dist)
		break_ = true;
	if(break_)return 0;
	if(dist < dis[x])return 0;
	
	if(x == 1 && dist == 0)
		return 1;
	if(rec.find(make_pair(x , dist)) != rec.end())
		return rec[make_pair(x , dist)];
	ll re = 0;
	int temp = goa[x];
	goa[x] = dist;
	for(int i = head2[x] ; i ; i = ed2[i].nxt){
		re += dfs(ed2[i].u , dist - ed2[i].len);
		re %= p;
	}
	goa[x] = temp;
	if(!break_)
		rec[make_pair(x , dist)] = re;
	return re;
}
int main(){
//	freopen("P3953_7.in" , "r" , stdin);
	int T = read();
	while(T--){
		addedge(-1 , -1 , 0);
		addedge(-1 , -1 , 0);
		memset(head , 0 , sizeof(head));
		memset(head2 , 0 , sizeof(head2));
		rec.clear();
		
		n = read();	m = read(); k = read(); p = read();
		for(int i = 1 ; i <= m ; i++){
			int u , v , len;
			u = read() , v = read() , len = read();
			addedge(u , v , len);
			addedge2(v , u , len);
		}
		spfa();
		if(dis[n] == 0){
			printf("-1
");
			continue;
		}
		sum = 0;
		break_ = false;
		
		for(int i = 0 ; i <= k && !break_; i++){
			memset(goa , -1 , sizeof(goa));
			sum = (sum + dfs(n , dis[n] + i)) % p;
		}
		sum = (sum + cnt[n]) % p;
		if(break_)sum = -1;
		printf("%d
" , (int)sum);
	}
	
	return 0;
} 

2版

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
#define ll long long
#define nn 1000010
using namespace std;
int read(){
	int re = 0 , sig = 1;
	char c = getchar();
	while(c < '0' || c > '9'){
		if(c == '-')sig = -1;
		c = getchar();
	}
	while(c >= '0' && c <= '9'){
		re = (re << 1) + (re << 3) + c - '0';
		c = getchar();
	}
	return re * sig;
}

struct ednode{
	int u , nxt , len;
}ed[nn * 2] , ed2[nn * 2];
int head[nn] , head2[nn];
inline void addedge(int u , int v , int len){
	static int top = 1;
	if(u == v && u == -1){top = 1;	return;}
	ed[top].u = v , ed[top].len = len , ed[top].nxt = head[u] , head[u] = top;
	top++;
}
inline void addedge2(int u , int v , int len){
	static int top = 1;
	if(u == v && u == -1){top = 1;	return;}
	ed2[top].u = v , ed2[top].len = len , ed2[top].nxt = head2[u] , head2[u] = top;
	top++;
}
int n , m , k ;
ll p;
int dis[nn] ;
ll cnt[nn];
bool vis[nn];
vector <int> from[nn];
void spfa(){
	memset(dis , 0x3f , sizeof(dis));
	memset(vis , 0 , sizeof(vis));
	
	queue <int> q;
	dis[1] = 0;
	vis[1] = true;
	q.push(1);
	while(!q.empty()){
		int k = q.front();
		q.pop();
		vis[k] = false;
		for(int i = head[k] ; i ; i = ed[i].nxt){
			if(dis[ed[i].u] > dis[k] + ed[i].len){
				dis[ed[i].u] = dis[k] + ed[i].len;
				from[ed[i].u].clear();
				if(!vis[ed[i].u]){
					q.push(ed[i].u);
					vis[ed[i].u] = true;
				}
			}
			if(dis[ed[i].u] == dis[k] + ed[i].len)
				from[ed[i].u].push_back(k);
				
		}
	}
}
ll sum;
int goa[nn];
int rec[nn][55];
bool break_;
ll dfs(int x , int dist) {
	if(dist == 0)return cnt[x];
	if(dist < 0)return 0;
	if(goa[x] == dist)
		break_ = true;
	if(break_)return 0;
	
	if(rec[x][dist] != -1)
		return rec[x][dist];
	rec[x][dist] = 0;
	int tmp = goa[x];
	goa[x] = dist;
	for(int i = head2[x] ; i ; i = ed2[i].nxt){
		rec[x][dist] += dfs(ed2[i].u , dist - ed2[i].len + (dis[x] - dis[ed2[i].u]));
		rec[x][dist] %= p;
	}
	goa[x] = tmp;
	return rec[x][dist];
}
void GetCnt(int x){
	if(cnt[x] != -1)return;
	cnt[x] = 0;
	for(int i = 0 ; i < from[x].size() ; i++){
		GetCnt(from[x][i]);
		cnt[x] += cnt[from[x][i]];
	}
	
}
int main(){
//	freopen("P3953_7.in" , "r" , stdin);
	int T = read();
	while(T--){
		addedge(-1 , -1 , 0);
		addedge(-1 , -1 , 0);
		memset(head , 0 , sizeof(head));
		memset(head2 , 0 , sizeof(head2));
		memset(rec , -1 , sizeof(rec));
		memset(cnt , -1 , sizeof(cnt));
		n = read();	m = read(); k = read(); p = read();
		for(int i = 1 ; i <= m ; i++){
			int u , v , len;
			u = read() , v = read() , len = read();
			addedge(u , v , len);
			addedge2(v , u , len);
		}
		spfa();
		cnt[1] = 1;
		for(int i = 1 ; i <= n ; i++)
			GetCnt(i);
		if(dis[n] == 0){
			printf("-1
");
			continue;
		}
		sum = 0;
		break_ = false;
		
		for(int i = 0 ; i <= k && !break_; i++){
			memset(goa , 0 , sizeof(goa));
			sum = (sum + dfs(n , i)) % p;
		}
		if(break_)sum = -1;
		printf("%d
" , (int)sum);
	}
	
	return 0;
}