生活大爆炸版石头剪刀布 模拟

题目链接

---

#include<cstdio>
int judge[5][5]={{0,-1,1,1,-1},
                  {1,0,-1,1,-1},
                  {-1,1,0,-1,1},
                  {-1,-1,1,0,1},
				  {1,1,-1,-1,0}};
int a[210],b[210];
int main()
{
	//freopen("in.txt","r",stdin);
	int sa=0,sb=0,n,ta,i,tb;
	scanf("%d%d%d",&n,&ta,&tb);
	for(i=0;i<ta;i++)
	scanf("%d",&a[i]);
	for(i=0;i<tb;i++)
	scanf("%d",&b[i]);
	for(i=0;i<n;i++)
	if(judge[a[i%ta]][b[i%tb]]==1)
	sa++;
	else if(judge[a[i%ta]][b[i%tb]]==-1)
	sb++;
	printf("%d %d\n",sa,sb);
	return 0;
}

总结

无

---

联合权值 乱搞

题目链接

---

处理出每个点相邻点的和，然后直接搞一搞

#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
const int N=2e5+10,mod=10007;
inline int read()
{
	int x=0,f=0;char ch=getchar();
	while(ch<'0'||ch>'9')f|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
	if(f)x=-x;return x;
}
int n,sum[N],w[N],m1,m2,maxn,ans;
vector<int>g[N];
int main()
{
	//freopen("in.txt","r",stdin);
	n=read();
	for(int i=1,u,v;i<n;i++)
	    u=read(),v=read(),g[u].push_back(v),g[v].push_back(u);
	for(int i=1;i<=n;i++)
	    w[i]=read();
	for(int i=1;i<=n;i++){
		m1=m2=0;
		for(int j=0;j<g[i].size();j++)
		{
			sum[i]=(sum[i]+w[g[i][j]])%mod;
			if(w[g[i][j]]>m1)m2=m1,m1=w[g[i][j]];
			else if(w[g[i][j]]>m2)m2=w[g[i][j]];
		}
		maxn=max(maxn,m1*m2);
    }
    printf("%d ",maxn);
	for(int i=1;i<=n;i++)
	    for(int j=0;j<g[i].size();j++)
	        ans=(ans+(sum[i]-w[g[i][j]]+mod)%mod*w[g[i][j]]%mod)%mod;
	printf("%d\n",ans);
	return 0;
}

总结

水题

---

飞扬的小鸟 背包问题

题目链接

---

一个综合性比较高的背包问题。要考虑的地方不少。

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=1e4+10,M=2e3+10;
int n,m,k,dp[N][M],x[N],y[N],exi[N],up[N],down[N],ans;
int main()
{
	//freopen("in.txt","r",stdin);
	scanf("%d%d%d",&n,&m,&k);
	for(int i=1;i<=n;i++)
	    scanf("%d%d",&x[i],&y[i]),down[i]=1,up[i]=m;//忘记了没有管道的地方也要赋值的 
	for(int i=1,p,l,h;i<=k;i++)
	{
		scanf("%d%d%d",&p,&l,&h);
		exi[p]=1;down[p]=l+1;up[p]=h-1;
	}
	memset(dp,0x3f,sizeof(dp));
	for(int i=1;i<=m;i++)
	    dp[0][i]=0;
	ans=dp[0][0];//dp[0][0]表示不可达 
	for(int i=1;i<=n;i++)
	{
		for(int j=x[i]+1;j<=x[i]+m;j++)//上升是完全背包，从i-1或者i转移过来 
		    dp[i][j]=min(dp[i][j-x[i]],dp[i-1][j-x[i]])+1;
		for(int j=m+1;j<=x[i]+m;j++)//特判飞到天花板的部分 
		    dp[i][m]=min(dp[i][m],dp[i][j]);
		for(int j=1;j<=m-y[i];j++)//下降是01背包 
		    dp[i][j]=min(dp[i][j],dp[i-1][j+y[i]]);
		for(int j=1;j<down[i];j++)//撞到下面 
		    dp[i][j]=dp[0][0];
		for(int j=up[i]+1;j<=m;j++)//撞到上面 
		    dp[i][j]=dp[0][0];
	} 
	for(int j=1;j<=m;j++)
	    ans=min(ans,dp[n][j]);
	if(ans<dp[0][0])printf("1\n%d\n",ans);
	else
	{
		int pos,find=0,cnt=0;
		for(pos=n;pos;pos--)
		{
		    for(int j=1;j<=m;j++)
		        if(dp[pos][j]<dp[0][0]){find=1;break;}
		    if(find)break;
	    }
	    for(int i=1;i<=pos;i++)
	        if(exi[i])cnt++;//i处有管道
		printf("0\n%d\n",cnt); 
	}
	return 0;
}

总结

实质是背包问题

---

无线网络发射器选址 树状数组

题目链接

题目描述

随着智能手机的日益普及，人们对无线网的需求日益增大。某城市决定对城市内的公共场所覆盖无线网。

假设该城市的布局为由严格平行的 129129 条东西向街道和 129129 条南北向街道所形成的网格状，并且相邻的平行街道之间的距离都是恒定值 11。东西向街道从北到南依次编号为 $0,1,2 \dots 1280$0,1,2…1280，南北向街道从西到东依次编号为 $0,1,2 \dots 128$0,1,2…128。

东西向街道和南北向街道相交形成路口，规定编号为 $x$x 的南北向街道和编号为 $y$y 的东西向街道形成的路口的坐标是 $(x, y)$(x,y)。在某些路口存在一定数量的公共场所。

由于*财政问题，只能安装一个大型无线网络发射器。该无线网络发射器的传播范围是一个以该点为中心，边长为 $2d$2d 的正方形。传播范围包括正方形边界。

现在*有关部门准备安装一个传播参数为 $d$d 的无线网络发射器，希望你帮助他们在城市内找出合适的路口作为安装地点，使得覆盖的公共场所最多。

输入输出格式

输入格式：

第一行包含一个整数 $d$d，表示无线网络发射器的传播距离。

第二行包含一个整数 $n$n，表示有公共场所的路口数目。

接下来 $n$n 行，每行给出三个整数 $x, y, k$x,y,k，中间用一个空格隔开，分别代表路口的坐标 $(x, y)$(x,y) 以及该路口公共场所的数量。同一坐标只会给出一次。

输出格式：
输出一行，包含两个整数，用一个空格隔开，分别表示能覆盖最多公共场所的安装地点方案数，以及能覆盖的最多公共场所的数量。

输入输出样例

输入样例#1：

1
2
4 4 10
6 6 20

输出样例#1：

1 30

说明

对于$100\%$100%的数据，$1 \leq d \leq 20, 0 \leq x \leq 128,0 &lt; k \leq 1000000$1≤d≤20,0≤x≤128,0<k≤1000000.

---

被普及-蒙蔽了双眼，觉得只要暴力就好，结果我暴力老是错……

#include<cstdio>
#include<algorithm>
using namespace std;
int c[1010][1010],n,d,maxn,cnt;
void add(int x,int y,int k)
{
	for(int i=x;i<=129+d;i+=i&(-i))
	for(int j=y;j<=129+d;j+=j&(-j))
	c[i][j]+=k;
}
int query(int x,int y)
{
	int ret=0;
	for(int i=x;i;i-=i&(-i))
	for(int j=y;j;j-=j&(-j))
	ret+=c[i][j];
	return ret;
}
int main()
{
	//freopen("in.txt","r",stdin);
    scanf("%d%d",&d,&n);int x,y,k;
    for(int i=1;i<=n;i++)
    {
    	scanf("%d%d%d",&x,&y,&k);x++;y++;
    	add(x,y,k);
	}
	for(int i=d+1;i<=129+d;i++)
	for(int j=d+1;j<=129+d;j++)
	{
		x=max(0,i-2*d-1),y=max(0,j-2*d-1);
		int ans=query(i,j)-query(x,j)-query(i,y)+query(x,y);
		if(maxn<ans)maxn=ans,cnt=1;
		else if(maxn==ans)cnt++;
	}
	printf("%d %d\n",cnt,maxn);
	return 0;
}

总结

我太菜了

---

寻找道路 最短路+bfs

题目链接

---

先在反图上宽搜一遍，标记出那些不能访问到的点。然后枚举不能访问的点，标记它在反图中指向的点为应删除，然后在原标记上修改。然后原图上跑spfa得到答案。

#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
inline int read()
{
	int x=0,f=0;char ch=getchar();
	while(ch<'0'||ch>'9')f|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
	if(f)x=-x;return x;
}
const int N=1e4+10,M=2e5+10;
int n,m,hd[N],hdn[N],dis[N],vis1[N],vis2[N],era[N],tot,totn,s,t;
struct Edge{
	int v,nx;
}e[M],ne[M];
inline void add(int u,int v)
{
	e[++tot].v=v;e[tot].nx=hd[u];hd[u]=tot;
	ne[++totn].v=u;ne[totn].nx=hdn[v];hdn[v]=totn;
}
inline void bfs()
{
	queue<int>q;while(!q.empty())q.pop();
	vis1[t]=1;q.push(t);vis2[t]=1; 
	while(!q.empty())
	{
		int u=q.front();q.pop();
		for(int i=hdn[u];i;i=ne[i].nx)
		{
			int v=ne[i].v;if(vis1[v])continue;
			q.push(v);vis1[v]=1;vis2[v]=1;
		}
	}
}
inline void spfa()
{
	memset(vis1,0,sizeof(vis1));memset(dis,0x3f,sizeof(dis));dis[s]=0;
	queue<int>q;while(q.size())q.pop();q.push(s);
	while(q.size())
	{
		int u=q.front();q.pop();vis1[u]=0;
		if(!vis2[u])continue;
		for(int i=hd[u];i;i=e[i].nx)
		{
			int v=e[i].v;
			if(dis[v]>dis[u]+1)
			{
				dis[v]=dis[u]+1;
				if(!vis1[v])vis1[v]=1,q.push(v);
			}
		}
	}
}
int main()
{
	//freopen("in.txt","r",stdin);
	n=read();m=read();
    for(int i=1,u,v;i<=m;i++)
        u=read(),v=read(),add(u,v);
    s=read();t=read();bfs();
    for(int i=1;i<=n;i++)
        if(!vis2[i])
            for(int j=hdn[i];j;j=ne[j].nx)
                era[ne[j].v]=1;
    for(int i=1;i<=n;i++)
        if(era[i])vis2[i]=0;
    spfa();
    if(dis[t]<0x3f3f3f3f)printf("%d\n",dis[t]);
    else puts("-1");
    return 0;
}

总结

基础图论，题意有点不好理解，根据样例解释理解

---

解方程 枚举+数学知识

题目链接

---

枚举答案x，计算上面那个式子的值，可以选择边算边模（某个八位质数），免得打高精，一般不会死。

#include<cstdio>
#include<vector>
using namespace std;
const int mod=19260817,M=1e6+10;
typedef long long ll;
template<typename tp>inline void read(tp &x)
{
	x=0;int f=0;char ch=getchar();
	while(ch<'0'||ch>'9')f|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9')x=((x<<1)%mod+(x<<3)%mod+(ch^48))%mod,ch=getchar();
	if(f)x=-x;
}
template<typename tp>inline void write(tp x)
{
	int buf[40],p=0;
	if(x<0)putchar('-'),x=-x;
	do{
		buf[p++]=x%10;x/=10;
	}while(x);
	for(int i=p-1;i+1;i--)putchar(buf[i]+48);
	putchar('\n');
}
ll n,m,a[110];
bool check(int x)
{
	int sum=0;
	for(int i=n;i;i--)
	    sum=(sum+a[i])*x%mod;
	sum=(sum+a[0]+mod)%mod;
	return !sum;
}
vector<int>v;
int main()
{
	//freopen("in.txt","r",stdin);
	read(n);read(m);
	for(int i=0;i<=n;i++)
	    read(a[i]);
	int flag=0,cnt=0;
	for(int i=1;i<=m;i++)
	    if(check(i)){cnt++;flag=1;v.push_back(i);}
	if(!flag)puts("0");
	else 
	{
		write(cnt);
		for(vector<int>::iterator it=v.begin();it!=v.end();it++)
		    write(*it);
	}
	return 0;
}

总结

通过模质数减小了题目难度。