首页 > 其他 > 详细

[考试总结]noip模拟6

时间：2021-06-12 01:24:15      阅读：23      评论：0      收藏：0      [点我收藏+]

我好菜啊

  • 真上次第二这次倒二。。。

因为昨天还没有改完所有的题所以就留到今天来写博客了

这次考试总结的教训有很多吧，反正处处体现XIN某人的laji，自己考试的是后本以为一共四个题目，三个题目都没有看懂，然而考试结束以后才发现，自己是四个题目都没有看懂。cao

又成10分XIN了

不管了，菜就是菜了。

以后看到题目中不懂的玩意儿也不应该害怕，什么曼哈顿距离，自己看看样例就知道了，不应该弃掉的，并且在手推样例认为样例有锅的时候也应该返回去去看看题目，而不是一味地认为题目有锅。。。

来自 \(\LaTeX\) 的侮辱

T1:

什么laji曼哈顿距离，反正对角线就完了。

。。。。。

然后记录每一个矩形，按照 \(x\) 的大小进行排序，之后就计算相邻矩形形成的氢键数量就 \(ok\) 了

为什么之考虑所有矩形不相连就有 \(65pts\) 啊！！！

。。。。。

code：

#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<queue>
#include<map>
using namespace std;
#define int long long
#define debug cout<<"debug"<<endl
#define freopen eat2 = freopen
#define scanf eat1 = scanf
namespace xin_io
{
	#define gc() p1 == p2 and (p2 = (p1 = buf) + fread(buf,1,1<<20,stdin),p1 == p2) ? EOF : *p1++
	#define scanf eat1 = scanf 
	#define freopen eat2 = freopen
	char buf[1<<20],*p1 = buf,*p2 = buf;FILE *eat2;
	inline void openfile() {freopen("t.txt","r",stdin);} inline void outfile(){freopen("o.txt","w",stdout);}
	inline int get()
	{
		int s = 0,f = 1;register char ch = gc();
		while(!isdigit(ch))
		{if(ch == ‘-‘) f = -1;ch = gc();}
		while(isdigit(ch))
		{s = s * 10 + ch - ‘0‘;ch = gc();}return s * f;
	}
}
using namespace xin_io; int eat1;
static const int maxn = 1e5+10;
#include<ctime>
#include<cstring>
#define mp make_pair
#define xd xin_data
#define rp(i,x,y) for(register int i=x;i<=y;++i)
#define bd(i,x,y) for(register int i=x;i>=y;--i)
namespace xin
{
	class xin_data
	{
		public:
			int x1,x2,y1,y2;
			friend bool operator < (xin_data x,xin_data y) {return x.x1 == y.x1 ? x.y1 < y.y1 : x.x1 < y.x1;}
	}p[maxn];
	int n,ans = 0;
	inline int find(int x,int y)
	{
		int tog;
		if(p[x].x2 + 1 == p[y].x1) 
		{
			if(p[y].y1 > p[x].y2 or p[y].y2 < p[x].y1) return 0;
			tog = abs(max(p[y].y2,p[x].y2) - min(p[y].y1,p[x].y1) + 1) - abs(p[y].y2 - p[x].y2) - abs(p[y].y1 - p[x].y1);
			if(p[x].y1 == p[y].y1 and p[x].y2 == p[y].y2) return tog * 2;
			if(p[x].y2 == p[y].y2 or p[x].y1 == p[y].y1) return tog * 2 - 1;
			return tog * 2;
		}
		if(p[x].y2 + 1 == p[y].y1)
		{
			if(p[y].x1 > p[x].x2 or p[x].x1 > p[y].x2) return 0;
			tog = abs(max(p[x].x2,p[y].x2) - min(p[x].x1,p[y].x1) + 1) - abs(p[x].x2 - p[y].x2) - abs(p[x].x1 - p[y].x1);
			if(p[x].x1 == p[y].x1 and p[x].x2 == p[y].x2) return tog * 2;
			if(p[x].x2 == p[y].x2 or p[x].x1 == p[y].x1) return tog * 2 - 1;
			return tog * 2;
		}
		return 0;
	}
	inline short main()
	{
	#ifndef ONLINE_JUDGE
		openfile();
	#endif
		n = get();
		rp(i,1,n) p[i].x1 = get(),p[i].y1 = get(),p[i].x2 = get(),p[i].y2 = get(),ans += (p[i].x2 - p[i].x1) * (p[i].y2 - p[i].y1) * 2;
		sort(p+1,p+n+1);
//		rp(i,1,n) cout<<"i = "<<i<<" p[i].x1 = "<<p[i].x1<<" p[i].y1 = "<<p[i].y1<<" p[i].x2 = "<<p[i].x2<<" p[i].y2 = "<<p[i].y2<<endl;
		rp(i,1,n)
			rp(j,i+1,n)
			{
				if(p[j].x1 - p[i].x2 > 1 ) break;
				if(min(p[i].x2,p[j].x2) - max(p[i].x1,p[j].x1) >= 0 and (p[i].y2 == p[j].y1 - 1 or p[j].y2 == p[i].y1 - 1))
				{
					if(p[i].y2 == p[j].y1 - 1)
					{
						ans += (min(p[i].x2,p[j].x2) - max(p[i].x1,p[j].x1)) * 2;
						if(p[i].x1 != p[j].x1) ans ++; if(p[i].x2 != p[j].x2) ans ++;
					}
					if(p[j].y2 == p[i].y1 - 1)
					{
						ans += (min(p[i].x2,p[j].x2) - max(p[i].x1,p[j].x1)) * 2;
						if(p[i].x1 != p[j].x1) ans ++; if(p[i].x2 != p[j].x2) ans ++;
					}
				}
				if(min(p[i].y2,p[j].y2) - max(p[i].y1 ,p[j].y1) >= 0 and (p[i].x2 == p[j].x1 - 1 or p[j].x2 == p[i].x1 - 1))
				{
					if(p[i].x2 == p[j].x1 - 1)
					{
						ans += (min(p[i].y2,p[j].y2) - max(p[i].y1,p[j].y1)) * 2;
						if(p[i].y1 != p[j].y1) ans ++; if(p[i].y2 != p[j].y2) ans ++;
					}
					if(p[j].x2 == p[i].x1 - 1)
					{
						ans += (min(p[i].y2,p[j].y2) - max(p[i].y1,p[j].y1)) * 2;
						if(p[i].y1 != p[j].y1) ans ++; if(p[i].y2 != p[j].y2) ans ++;
					}
				}
				if(p[i].x2 == p[j].x1 - 1 and (p[i].y2 == p[j].y1 - 1 or p[i].y1 == p[j].y2 + 1)) ans++;
				///cout<<"i = "<<i<<" ans = "<<ans<<endl;
			}
		cout<<ans<<endl;
		return 0;
	}
}
signed main() {return xin::main();}

T2:

。。。。。

我不会告诉你我还没有调出来。。。。

T3:

又是 \(dark\) 佬。。。。

设 \(f\) 表示概率，那么我们就可以知道：

\[f_i=f_{i-1}-sum_{i-1} \]

\[sum_{i-1} = \sum_{i=1}^{i-1} f_i \]

\[ans=\sum w_i * f_i \]

。。。。

所以\(code:\)



#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
#define int long long
#define debug cout<<"debug"<<endl
#define freopen eat2 = freopen
#define scanf eat1 = scanf
namespace xin_io
{
	#define gc() p1 == p2 and (p2 = (p1 = buf) + fread(buf,1,1<<20,stdin),p1 == p2) ? EOF : *p1++
	#define scanf eat1 = scanf 
	#define freopen eat2 = freopen
	char buf[1<<20],*p1 = buf,*p2 = buf;FILE *eat2;
	inline void openfile() {freopen("t.txt","r",stdin);} inline void outfile(){freopen("o.txt","w",stdout);}
	inline int get()
	{
		int s = 0,f = 1;register char ch = gc();
		while(!isdigit(ch))
		{if(ch == ‘-‘) f = -1;ch = gc();}
		while(isdigit(ch))
		{s = s * 10 + ch - ‘0‘;ch = gc();}return s * f;
	}
}
using namespace xin_io; int eat1;
static const int maxn = 1e5+10,mod = 1000000007;
#include<ctime>
#include<cstring>
namespace xin
{
	int n,m,k;
	int w[maxn];
	inline int ksm(int x,int y,int mod)
	{
		int ret = 1;
		while(y){if(y & 1) ret = ret * x % mod;x = x * x % mod; y >>= 1;}
		return ret;
	}
	inline int inv(int x) {return ksm(x,mod-2,mod);}
	int f[maxn],ans,s;
	inline short main()
	{
	#ifndef ONLINE_JUDGE
		openfile();
	#endif
		n = get(); m = get(); k = get();
		int day = (n - k + 1) > 0 ? (n - k + 1) : 0;
		for(register int i=1;i<=m;++i) w[i] = get();//,w[i] = w[i-1] + w[i];
		for(register int i=1;i<=m;++i)
		{
			s = s + f[i-1] % mod;
			f[i] = (ksm(i,k,mod) * inv(ksm(m,k,mod)) - s) % mod;
			ans = (ans + w[i] * f[i]) % mod;
		}
		ans = ans * day % mod;
		cout<<ans<<endl;
		return 0;
	}
}
signed main() {return xin::main();}

T4:

暴搜。。。

只需要考虑每一个起始点和每一个结束点。。。

然后开始暴搜。。。

不需要建边，只要维护一个 \(cost\) 数组就行了。。。

\(cost\) 初始值就设置为 \(0x7f7f7f7f7f\) 就行。。。

最后取得最小值。

一共 \(n <= 12\) ，然而 \(m\) 却$ <=2000$ ，重边很多。。。

之后就有 \(70pts\) 了



#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
#define int long long
#define debug cout<<"debug"<<endl
#define freopen eat2 = freopen
#define scanf eat1 = scanf
namespace xin_io
{
	#define gc() p1 == p2 and (p2 = (p1 = buf) + fread(buf,1,1<<20,stdin),p1 == p2) ? EOF : *p1++
	#define scanf eat1 = scanf 
	#define freopen eat2 = freopen
	char buf[1<<20],*p1 = buf,*p2 = buf;FILE *eat2;
	inline void openfile() {freopen("t.txt","r",stdin);} inline void outfile(){freopen("o.txt","w",stdout);}
	inline int get()
	{
		int s = 0,f = 1;register char ch = gc();
		while(!isdigit(ch))
		{if(ch == ‘-‘) f = -1;ch = gc();}
		while(isdigit(ch))
		{s = s * 10 + ch - ‘0‘;ch = gc();}return s * f;
	}
}
using namespace xin_io; int eat1;
static const int maxn = 13;
#include<ctime>
#include<cstring>
#define m(c,num) memset(c,num,sizeof c)
namespace xin
{
	int n,m;
	int c[maxn][maxn];
	int temp;
	int num[maxn];
	int ans = 0x7f7f7f7f;
	void dfs(int now,int cnt)
	{
		if(cnt == n)
		{
			ans = min(ans,temp);
			return ;
		}
		if(temp >= ans) return ;
		for(register int i=1;i<=n;++i)
			if(!num[i])
				for(register int j=1;j<=n;++j)
					if(c[i][j] != 0x7f7f7f7f and i != j and num[j])
					{
						temp += num[j] * c[i][j]; num[i] = num[j] + 1;
						dfs(i,cnt+1);
						temp -= num[j] * c[i][j]; num[i] = 0;
					}
	}
	inline short main()
	{
	#ifndef ONLINE_JUDGE
		openfile();
	#endif
		n = get(); m = get(); for(register int i=1;i<=n;++i) for(register int j=0;j<=n;++j) c[i][j] = 0x7f7f7f7f;
		for(register int i=1;i<=m;++i)
		{
			register int x = get(),y = get();
			c[x][y] = c[y][x] = min(c[x][y],get()); 
		}
		for(register int i=1;i<=n;++i)
		{num[i] = 1; dfs(i,1); num[i] = 0;}
		cout<<ans<<endl;
		return 0;
	}
}
signed main() {return xin::main();}

之后考虑正解，实际上就是有枝就剪。

然后飞快。。。



#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
//#define int long long
#define debug cout<<"debug"<<endl
#define freopen eat2 = freopen
#define scanf eat1 = scanf
#define inf 0x7f7f7f7f
namespace xin_io
{
	#define gc() p1 == p2 and (p2 = (p1 = buf) + fread(buf,1,1<<20,stdin),p1 == p2) ? EOF : *p1++
	#define scanf eat1 = scanf 
	#define freopen eat2 = freopen
	char buf[1<<20],*p1 = buf,*p2 = buf;FILE *eat2;
	inline void openfile() {freopen("t.txt","r",stdin);} inline void outfile(){freopen("o.txt","w",stdout);}
	inline int get()
	{
		int s = 0,f = 1;register char ch = gc();
		while(!isdigit(ch))
		{if(ch == ‘-‘) f = -1;ch = gc();}
		while(isdigit(ch))
		{s = s * 10 + ch - ‘0‘;ch = gc();}return s * f;
	}
}
using namespace xin_io; int eat1;
static const int maxn = 13;
#include<ctime>
#include<cstring>
#define m(c,num) memset(c,num,sizeof c)
namespace xin
{
	int n,m;
	int vis[maxn],rea[maxn][maxn],tot;
	int c[maxn][maxn],d[maxn],l[maxn];
	int temp,cnt;
	int ans = inf;
	inline void dfs(int num,int nd)
	{
		for(register int i=num;i<=cnt;++i)
		{
			if(tot + temp * l[vis[i]] >= ans) return;
			for(register int j=nd;j<=d[vis[i]];++j)
				if(!l[rea[vis[i]][j]])
				{
					vis[++cnt] = rea[vis[i]][j];
					temp -= c[vis[cnt]][rea[vis[cnt]][1]];
					tot += c[vis[i]][vis[cnt]] * l[vis[i]];
					l[vis[cnt]] = l[vis[i]] + 1;
					dfs(i,j+1);
					temp += c[vis[cnt]][rea[vis[cnt]][1]];
					tot -= c[vis[i]][vis[cnt]] * l[vis[i]];
					l[vis[cnt]] = 0;cnt--;
				}
				nd = 1;
		}
		if(cnt == n) {ans = min(ans,tot);return ;}
	}
	int pai;
	inline bool comp(int x,int y) {return c[pai][x] < c[pai][y];}
	inline short main()
	{
	#ifndef ONLINE_JUDGE
		openfile();
	#endif
		n = get(); m = get(); for(register int i=1;i<=n;++i) for(register int j=1;j<=n;++j) c[i][j] = inf; 
		for(register int i=1;i<=m;++i)
		{
			register int x = get(),y = get(),z = get();
			if(z <= c[x][y])
			{
				if(c[x][y] == inf) rea[x][++d[x]] = y,rea[y][++d[y]] = x;
				c[x][y] = c[y][x] = z;
			}
		}
		for(register int i=1;i<=n;++i)
		{	
			pai = i; sort(rea[i]+1,rea[i]+d[i]+1,comp);
			temp += c[i][rea[i][1]];
		}
		for(register int i=1;i<=n;++i)
		{
			cnt = 1; tot = 0;
			temp -= c[i][rea[i][1]];
			vis[1] = i;
			l[i] = 1;
			dfs(1,1);
			temp += c[i][rea[i][1]];
			l[i] = 0;
		}
		printf("%d\n",ans);
		return 0;
	}
}
signed main() {return xin::main();}

[考试总结]noip模拟6

原文：https://www.cnblogs.com/NP2Z/p/14876570.html
踩
(0)
赞
(0)
   
举报
评论 一句话评论（0）
分享档案
更多>
2021年09月23日 (328)
2021年09月24日 (313)
2021年09月17日 (191)
2021年09月15日 (369)
2021年09月16日 (411)
2021年09月13日 (439)
2021年09月11日 (398)
2021年09月12日 (393)
2021年09月10日 (160)
2021年09月08日 (222)
最新文章
更多>
教程昨日排行
更多>
友情链接
汇智网   PHP教程   插件网  
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣，分享程序人生！