首页 > 其他分享 >20220920测试总结

20220920测试总结

时间：2022-09-20 16:56:08浏览次数：110  
标签：总结 20220920 ch int sum 1ll 测试 include ll

题目还是挺爽的。

P2327 [SCOI2005]扫雷

原题链接

题目分析

我们设\(a[i]\)为第\(i\)行的数字，显然如果满足\(a[1]=3\vee a[n]=3\)时，方案数为\(0\)呐等于\(0\)。

所以接下来我们考虑搜索，设\(v[i]\)（\(bool\)类型）为第\(i\)行是否放了地雷（\(1\)表示放置，\(0\)表示没有放置）。

对于\(a[i]=3\)的情况，只需要将\(v[i-1],v[i]\)和\(v[i+1]\)赋为\(1\)即可。

接下来考虑\(a[i]=1\)和\(a[i]=2\)。

显然，当\(i-1\)至\(i+1\)范围中雷的个数\(sum=a[i]\)时，直接往后搜索即可，如果不等于，就要放置地雷来满足\(sum=a[i]\)，同时需要考虑当前放置的棋子对之前放置的棋子产生的影响，所以在搜索中笔者记录了前两个格子分别在\(i-1\)至\(i+1\)内地雷个数，如果当前放置地雷位置导致了之前格子所包含的地雷数过多，或者此位置已经放置了地雷，则重新枚举位置。

点击查看代码 
#include <cmath>
#include <ctime>
#include <cstdio>
#include <cctype>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#define ll long long
#define R register
using namespace std;
int n;
int a[10005];
bool v[10005];
ll ans;

inline ll re(){
    R ll k=0,f=1ll;
    R char ch=getchar();
    while(!isdigit(ch)){
	if(ch=='-')
	    f=-1ll;
       	ch=getchar();
    }
    while(isdigit(ch)){
	k=k*10ll+(ch^48ll);
	ch=getchar();
    }
    return 1ll*k*f;
}

void wr(ll x){
    if(x<0){
        putchar('-');
	x=~x+1;
    }
    if(x>9)
	wr(x/10ll);
    putchar(x%10+48ll);
}

void dfs(int x,int la,int s,int lla,int ss){	//记录前两个格子位置以及在格子范围内地雷个数
    if(!x){
        ++ans;
	return;
    }
    R int sum=0;
    R int down=min(n,x+1),up=max(1,x-1);
    for(R int i=down;i>=up;--i)
	if(v[i])
            ++sum;
	if(sum>a[x])
	    return;
	if(sum==a[x]){
	    dfs(x-1,x,sum,la,s);
	    return;
	}
	for(R int i=down;i>=up;--i){
            if(v[i])
                continue;
	    if(a[x]==2){
		if(i==x+1){
		    if((s+1!=a[la]||ss+1!=a[lla])&&la<=n&&lla<=n)	//是否对之后状态产生影响
		        continue;
		    v[i]=1,++sum;
		    if(sum==1){
		        for(R int j=i-1;j>=up;--j){
			    if(j==x){
				if(s+1!=a[la])
				    continue;
				v[j]=1;
				++sum;
				dfs(x-1,x,sum,la,s);
				--sum;
				v[j]=0;
			    }
			}
			v[i]=0,--sum;
		    }
		    else if(i==x){
			if(s+1!=a[la]&&la<=n)	//是否对之后状态产生影响
			    continue;
			v[i]=1,++sum;
			if(sum==1){
			    v[i-1]=1,++sum;
			    dfs(x-1,x,sum,la,s);
			    v[i-1]=0,--sum;
			}
			v[i]=0,--sum;
		     }
		     else if(i==x-1){
			v[i]=1,++sum;
			if(sum!=a[x]) continue;
			dfs(x-1,x,sum,la,s);
			v[i]=0,--sum;
		     }
		}
		else if(a[x]==1){
		    if(i==x+1){
		        if((s+1!=a[la]||ss+1!=a[lla])&&la<=n&&lla<=n)
			    continue;
			    v[i]=1,++sum;
			    dfs(x-1,x,sum,la,s);
			    v[i]=0,--sum;
		    }
		    else if(i==x){
			if(s+1!=a[la]&&la<=n)
			    continue;
			    v[i]=1,++sum;
			    dfs(x-1,x,sum,la,s);
			    v[i]=0,--sum;
		    }
		    else if(i==x-1){
			v[i]=1,++sum;
			dfs(x-1,x,sum,la,s);
			v[i]=0,--sum;
		    }
		}
		else
		    dfs(x-1,x,sum,la,s);
	}
}

signed main(){
    n=re();
    for(R int i=1;i<=n;++i){
        a[i]=re();
	if(a[i]>=3){
	    a[i]=3;
	    if(a[1]==3||a[n]==3){
                puts("0");
		return 0;
	    }
	    v[i]=v[i-1]=v[i+1]=1;
	}
    }
    dfs(n,n+1,0,n+2,0);
    wr(ans);
    return 0;
}

P1896 [SCOI2005] 互不侵犯

原题链接

题目分析

经典状压dp

令\(f[i][j][l]\)为前\(i\)行放置了\(l\)个国王，第\(i\)行状态为\(j\)的方案数

所以\(f[i][j][l]+=f[i-1][k][l-king[k]]\)，其中\(k\)为第\(i-1\)行的状态，\(king[k]\)为状态\(k\)的国王个数

计算是否冲突有：

  1. \(sit[j]\&sit[k]\)

  2. \((sit[j]<<1)\&sit[k]\)

  3. \(sit[j]\&(sit[k]<<1)\)

于是完事儿

点击查看代码 
#include <cmath>
#include <cctype>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#define ll long long
using namespace std;
ll n,m,cnt,ans;
ll sit[2010],king[2010];
ll f[15][2010][95];

inline ll re(){
    ll k=0,f=1ll;
    char ch=getchar();
    while(!isdigit(ch)){
	if(ch=='-')
	    f=-1ll;
       	ch=getchar();
    }
    while(isdigit(ch)){
	k=k*10ll+(ch^48ll);
	ch=getchar();
    }
    return 1ll*k*f;
}

void wr(ll x){
    if(x<0){
        putchar('-');
	x=~x+1;
    }
    if(x>9)
	wr(x/10ll);
    putchar(x%10+48ll);
}

inline void init_(int one,int kin,int now){
    if(now>=n){
	sit[++cnt]=one;
	king[cnt]=kin;
	return;
    }
    init_(one,kin,now+1);
    init_(one+(1<<now),kin+1,now+2);
}

signed main(){
    n=re(),m=re();
    init_(0,0,0);
    for(int i=1;i<=cnt;++i)
	f[1][i][king[i]]=1;
    for(int i=2;i<=n;++i){
	for(int j=1;j<=cnt;++j){
	    for(int k=1;k<=cnt;++k){
		if(sit[j]&sit[k]||(sit[j]<<1)&sit[k]||sit[j]&(sit[k]<<1))
		    continue;
		for(int l=m;l>=king[k];--l)
		    f[i][j][l]+=f[i-1][k][l-king[j]];
	    }
	}
    }
    for(int i=1;i<=cnt;++i)
	ans+=f[n][i][m];
    wr(ans);
    return 0;
}

P2330 [SCOI2005]繁忙的都市

原题链接

超级大水题之sort中把E+1+m写成E+1+n丢掉100pts​

题目分析

显然就是一个求出最小生成树中的最大权值，由于按照权值排序，所以当符合条件的边个数达到\(n-1\)时输出第\(n-1\)条符合条件的边的权值即可

点击查看代码 
#include <cmath>
#include <cstdio>
#include <cctype>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#define ll long long
using namespace std;
ll ans;
int n,m;
int fa[305];

inline ll re(){
    ll k=0,f=1ll;
    char ch=getchar();
    while(!isdigit(ch)){
	if(ch=='-')
	    f=-1ll;
       	ch=getchar();
    }
    while(isdigit(ch)){
	k=k*10ll+(ch^48ll);
	ch=getchar();
    }
    return 1ll*k*f;
}

void wr(ll x){
    if(x<0){
        putchar('-');
	x=~x+1;
    }
    if(x>9)
	wr(x/10ll);
    putchar(x%10+48ll);
}

struct Edge{
    int u,v,w;
}E[100005];

inline bool cmp(Edge a,Edge b){
    return a.w<b.w;
}

int find_(int x){
    return (x==fa[x])?x:(fa[x]=find_(fa[x]));
}

signed main(){
    n=re(),m=re();
    for(int i=1;i<=n;++i) fa[i]=i;
    for(int i=1,u,v,w;i<=m;++i){
	u=re(),v=re(),w=re();
	E[i].u=u,E[i].v=v,E[i].w=w;
    }
    sort(E+1,E+1+m,cmp);
    int cnt=0;
    for(int i=1;i<=m;++i){
	int u=E[i].u,v=E[i].v;
	int x=find_(u);
	int y=find_(v);
	if(x!=y){
	    fa[x]=y;
	    int w=E[i].w;
	    ans=w;
	    ++cnt;
	    if(cnt==n-1) break;
	}
    }
    wr(n-1),putchar(' '),wr(ans);
    return 0;
}

P2331 [SCOI2005]最大子矩阵

原题链接

爽题

题目分析

当\(m=1\)时，就是一个最大子段和问题，所以设\(f_1[i][j]\)为在\(i\)位置已经有\(j\)个矩阵时的最大和

那我们的状态就有两种：

  1. 不选择一段区间

    \[f_1[i][j]=f_1[i-1][j] \]

  2. 选择一段区间

\[f_1[i][j]=\max\{f_1[k][j-1]+sum[i]-sum[k]\} \]

其中\(sum[i]\)表示以\(i\)点结尾的前缀和，目标状态：\(f_1[n][K]\)

当\(m=2\)时，情况有些复杂，不妨将其看作是两个\(m=1\)的段拼凑在一起，所以我们的状态设置就可以有\(f_2[i][j][k]\)表示在第1列以\(i\)结尾，第2列以\(j\)结尾，已经选了\(k\)个矩阵的最大和，所以我们设\(sum_1[i]\)为第一列中\(i\)的前缀和，\(sum_2[i]\)表示第二列中\(i\)的前缀和

下面，我们一一来分析状态：

  1. 既不选择\(i\)点的数，也不选择\(j\)点的数

\[f_2[i][j][k]=\max\{f_2[i-1][j][k],f_2[i][j-1][k]\} \]

  1. 仅选择第1列的一段区间

\[f_2[i][j][k]=\max\{f_2[l][j][k-1]+sum_1[i]-sum_1[l]\} \]

  1. 仅选择第2列的一段区间

\[f_2[i][j][k]=\max\{f_2[i][l][k-1]+sum_2[j]-sum_2[l]\} \]

  1. 二者都选，当且仅当\(i=j\)

\[f_2[i][j][k]=\max\{f_2[l][l][k-1]+sum_1[i]-sum_1[l]+sum_2[j]-sum_2[l]\} \]

目标状态：\(f[n][n][K]\)

点击查看代码 
#include <cmath>
#include <cstdio>
#include <cctype>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#define ll long long
using namespace std;
int n,m,K;
int sum1[105],sum2[105];
int f1[105][15],f2[105][105][15];

inline ll re(){
    ll k=0,f=1ll;
    char ch=getchar();
    while(!isdigit(ch)){
	if(ch=='-')
	    f=-1ll;
       	ch=getchar();
    }
    while(isdigit(ch)){
	k=k*10ll+(ch^48ll);
	ch=getchar();
    }
    return 1ll*k*f;
}

void wr(ll x){
    if(x<0){
        putchar('-');
	x=~x+1;
    }
    if(x>9)
	wr(x/10ll);
    putchar(x%10+48ll);
}

signed main(){
    n=re(),m=re(),K=re();
    if(m&1){
	for(int i=1;i<=n;++i){
	    int x=re();
	    sum1[i]=sum1[i-1]+x;
	}
	for(int k=1;k<=K;++k){
	    for(int i=1;i<=n;++i){
		f1[i][k]=f1[i-1][k];
		for(int j=0;j<i;++j)
		    f1[i][k]=max(f1[i][k],f1[j][k-1]+sum1[i]-sum1[j]);
	    }
	}
	wr(f1[n][K]);
    }
    else{
	for(int i=1;i<=n;++i){
	    int x=re(),y=re();
	    sum1[i]=sum1[i-1]+x,sum2[i]=sum2[i-1]+y;
	}
	for(int k=1;k<=K;++k){
	    for(int i=1;i<=n;++i){
		for(int j=1;j<=n;++j){
		    f2[i][j][k]=max(f2[i-1][j][k],f2[i][j-1][k]);
		    for(int l=0;l<i;++l)
			f2[i][j][k]=max(f2[i][j][k],f2[l][j][k-1]+sum1[i]-sum1[l]);
			for(int l=0;l<j;++l)
			    f2[i][j][k]=max(f2[i][j][k],f2[i][l][k-1]+sum2[j]-sum2[l]);
			    if(i==j)
			        for(int l=0;l<i;++l)
				    f2[i][j][k]=max(f2[i][j][k],f2[l][l][k-1]+sum1[i]+sum2[j]-sum1[l]-sum2[l]);
		}
	    }
	}
	wr(f2[n][n][K]);
    }
    return 0;
}

标签：总结,20220920,ch,int,sum,1ll,测试,include,ll
From： https://www.cnblogs.com/WXDreemurr/p/16711629.html

相关文章

  • .NET 6 EFCore WebApi 使用 JMeter 进行吞吐量测试
    .NET6EFCoreWebApi使用JMeter进行吞吐量测试开发环境VS2022.NET6测试环境测试工具接口压力测试工具：JMeter数据库MySQL5.7数据库和WebApi服务在同一台服务......
  • UI自动化测试之五（UnitTest测试框架）
    UnitTest测试框架 1、测试用例 2、完整的测试流程需包含：初始化测试步骤（1）、先执行setup（）（2）、执行测试点的代码（3）、最后执行tearDown（）测试断言（1）、in   关键字：as......
  • 集群启动/停止方式总结
    1）各个模块分开启动/停止（配置ssh是前提）常用（1）整体启动/停止HDFSstart-dfs.sh/stop-dfs.sh（2）整体启动/停止YARNstart-yarn.sh/stop-yarn.sh2）各个服务组件逐一启动/停......
  • JAVA SE 基础总结
    §基础知识一、程序组织与运行原理1.1程序组织一个JAVA程序文件中主要由如下几部分构成：package声明public类：public类与类文件名相同，因为其是作为该类文件......
  • 每日总结
    1、对于LeetCode297.二叉树的序列化与反序列化而言。需要注意的是递归出口的灵活应用，以及递归的深层理解。尤其对于链表、树、图这三种数据结构而言，递归的使用非常频繁。......
  • 【AGC】A/B测试场景问题
    ​背景：【A/B测详情询问】平台的AB测功能分的比较详细，如果只是需要测试icon五图的话是需要选择哪种类型，另外是否需要发邮件开通功能呢。​ 问题：开发者在创建A/B测试时......
  • 2022第五空间-web部分wp+复盘总结
    打了一天，麻了，大佬tql，这次get到了不少东西，一是一个不太常见的宽字节注入，我是真的没想到，而且后面也是看了wp理解了好一会才弄明白。0x01:题目是一个登录框，但是基本上是过滤......
  • Oracle元数据查询总结
     selectDISTINCT(OWNER)fromall_tablesselectTABLE_NAMEfromall_tableswhereOWNER='WZZLSDB'selectA.OWNER,A.TABLE_NAME,A.NUM_ROWS,A.NUM_ROWS*A.......
  • 前端面试总结02-变量类型和计算
    值类型与引用类型值类型：   引用类型常见值类型：consta//undefinedconsts='abc'constn=100constb=trueconsts=Symbol('s')常见引用类型：constobj={x:......
  • 浅谈Flexray基础通讯测试
      随着车载网络发展，ECU的通讯速率相较以往得到飞速提升。现今多数OEM在中高速通讯场景中仍采用CANFD进行过渡，但当同时考虑安全和更高带宽要求时，CANFD则无法满足，FlexRay则......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99