导语
这场打的还可以，也学到了二分图的更简单的建图和匹配实现，虽然以前看过，但没有着重关注，这次直接整理了
涉及的知识点
二分图，模拟，递推
链接：训练赛 [Cloned]
题目
H
题目大意：略
思路：这道题给了一个启示，小的细节优化往往能带来出其不意的效果
思路是直接模拟暴力，但是如果直接从整个大平面空间逐个遍历显然是不合算的，可以发现，活着的细胞相比于整个平面空间都是少数，那么可以从这一部分入手，我们记录活着的人存在的区域，或者说涉及到的区域，每次对这个区域进行一次遍历，并判断是否产生了拓展，如果区域被拓展，那么更新即可，这样的总体复杂度会很低
代码
#include<bits/stdc++.h>
using namespace std;
int t,n,m;
int a[700][700],b[700][700];
int getAround(bool flag,int x,int y) {
int sum=0;
if(flag) {
sum-=a[x][y];
for(int i=-1; i<=1; i++)
for(int j=-1; j<=1; j++)
sum+=a[x+i][y+j];
} else {
sum-=b[x][y];
for(int i=-1; i<=1; i++)
for(int j=-1; j<=1; j++)
sum+=b[x+i][y+j];
}
return sum;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >>t;
while(t--) {
cin >>n>>m;
memset(a,0,sizeof(a));
memset(b,0,sizeof(b));
char ch;
int sum=0,mx=0,pos=0,d=350,u=350+5,l=350,r=350+5;
for(int i=0; i<n; i++)
for(int j=0; j<m; j++) {
cin >>ch;
if(ch=='#')
a[350+i][350+j]=1,sum++,mx++;
}
for(int i=1; i<=321; i++) {
sum=0;
if(i&1) {
for(int i=d-1; i<=u+1; i++)
for(int j=l-1; j<=r+1; j++) {
int res=getAround(1,i,j);
b[i][j]=a[i][j];
if((res<2||res>3)&&a[i][j])b[i][j]=0;
else if(res==3&&!a[i][j])b[i][j]=1;
sum+=b[i][j];
if(b[i][j]) {
if(i==d-1)d--;
else if(i==u+1)u++;
if(j==l-1)l--;
else if(j==r+1)r++;
}
}
} else {
for(int i=d-1; i<=u+1; i++)
for(int j=l-1; j<=r+1; j++) {
int res=getAround(0,i,j);
a[i][j]=b[i][j];
if((res<2||res>3)&&b[i][j])a[i][j]=0;
else if(res==3&&!b[i][j])a[i][j]=1;
sum+=a[i][j];
if(a[i][j]) {
if(i==d-1)d--;
else if(i==u+1)u++;
if(j==l-1)l--;
else if(j==r+1)r++;
}
}
}
if(sum>mx)pos=i,mx=sum;
}
cout <<pos<<" "<<mx<<" "<<sum<<endl;
}
return 0;
}
I
题目大意：给出一共4×4矩阵，A和B对矩阵轮流操作，A先操作，每次操作选择一个2×2的矩阵，统计矩阵元素和加在总分数上，然后将这个2×2矩阵逆时针旋转90度，一共进行k轮，也就是2k次操作，A的目标是使得总分数最大，B的目标是使得总分数最小，计算两人在最优策略下最后获得的总分数
思路：直接暴力，可以计算出总时间复杂度由于数据范围很小
代码
#include<bits/stdc++.h>
using namespace std;
int t,n,m,k,a[12][12];
int getsum(int x,int y) {
return a[x][y]+a[x+1][y]+a[x][y+1]+a[x+1][y+1];
}
void up(int x,int y) {
int tmp=a[x][y];
a[x][y]=a[x][y+1];
a[x][y+1]=a[x+1][y+1];
a[x+1][y+1]=a[x+1][y];
a[x+1][y]=tmp;
}
void down(int x,int y) {
int tmp=a[x][y];
a[x][y]=a[x+1][y];
a[x+1][y]=a[x+1][y+1];
a[x+1][y+1]=a[x][y+1];
a[x][y+1]=tmp;
}
int DFS(int level) {
if(level==2*k) {
int mn=0x3f3f3f3f;
for(int i=1; i<4; i++)
for(int j=1; j<4; j++)
mn=min(mn,getsum(i,j));
return mn;
}
if(level&1) {
int mx=0;
for(int i=1; i<4; i++)
for(int j=1; j<4; j++) {
up(i,j);
int sum=getsum(i,j)+DFS(level+1);
mx=max(mx,sum);
down(i,j);
}
return mx;
}
int mn=0x3f3f3f3f;
for(int i=1; i<4; i++)
for(int j=1; j<4; j++) {
up(i,j);
int sum=getsum(i,j)+DFS(level+1);
mn=min(mn,sum);
down(i,j);
}
return mn;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >>t;
while(t--) {
cin >>k;
for(int i=1; i<=4; i++)
for(int j=1; j<=4; j++)
cin >>a[i][j];
cout <<DFS(1)<<endl;
}
return 0;
}
M
题目大意：给出一共有向无环图
G
G
G，定义一个点集
V
U
R
?
V
V_UR?V
VU?R?V作为
G
G
G的不可达集，集合中的任意两点
u
,
v
u,v
u,v两者间都不存在路径可到达彼此，求出
G
G
G的最大不可达集的大小
思路：很显然图被分成了两个集合，那么求的就是二分图的最大独立集，由于点很少，直接用矩阵存即可，跑最大匹配，最大独立集=总结点数-最大匹配
代码
#include <bits/stdc++.h>
using namespace std;
const int maxn=1e5+5;
const int inf=0x3f3f3f3f;
int n,m,match[121],res;
bool graph[121][121],vis[121];
bool maxmatch(int u) {
for(int v=1; v<=n; v++) {
if(!vis[v]&&graph[u][v]) {
vis[v]=1;
if(match[v]==-1||maxmatch(match[v])) {
match[v]=u;
return 1;
}
}
}
return 0;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int T;
cin >>T;
while(T--) {
cin >>n>>m;
memset(graph,0,sizeof(graph));
while(m--) {
int u,v;
cin >>u>>v;
graph[u][v]=1;
}
memset(match,-1,sizeof(match));
res=0;
for(int i=1; i<=n; i++)
for(int j=1; j<=n; j++)
for(int k=1; k<=n; k++)
graph[i][j]|=graph[i][k]&graph[k][j];
for(int i=1; i<=n; i++) {
memset(vis,0,sizeof(vis));
if(maxmatch(i))res++;
}
cout <<n-res<<endl;
}
return 0;
}
L
题目大意：给出一个正整数
L
L
L，找到一个最小的不小于
L
L
L的整数
n
n
n，使得存在一个正整数
m
m
m满足等式
2
m
(
m
+
1
)
=
n
(
n
+
1
)
2m(m+1)=n(n+1)
2m(m+1)=n(n+1)
思路：首先数据量给的很大，因此线性遍历是不可能的，并且需要使用大数来进行存储与运算，因此使用Java语言，将等式中的
n
n
n视为已知，那么最后可以得到
m
m
m的表达式：
1
+
2
n
2
+
2
n
/
2
?
1
/
2
\sqrt{1+2n^2+2n}/2-1/2
1+2n2+2n
?/2?1/2，打表可以得到符合条件的
n
n
n的递推式：
a
[
i
]
=
(
a
[
i
?
1
]
+
a
[
i
?
2
]
)
?
5
+
4
?
a
[
i
?
3
]
a[i]=(a[i-1]+a[i-2])*5+4-a[i-3]
a[i]=(a[i?1]+a[i?2])?5+4?a[i?3]
代码
import java.math.BigInteger;
import java.util.Scanner;
public class Main {
static BigInteger a[]= new BigInteger[2010];
public static void main(String[] args) {
init();
Scanner inputScanner=new Scanner(System.in);
int t = inputScanner.nextInt();
for(int i = 1;i <= t;i++)
{
String string = inputScanner.next();
BigInteger lBigInteger = new BigInteger(string);
int l = 0;
int r = 2000;
if(lBigInteger.compareTo(a[l])<=0) {
System.out.println(a[l].toString());
}
else {
while(l<r)
{
int mid = (l+r)/2;
if(a[mid].compareTo(lBigInteger)>=0)
{
r=mid;
}
else {
l=mid+1;
}
}
System.out.println(a[l].toString());
}
}
}
static void init() {
a[0]=new BigInteger("3");
a[1]=new BigInteger("20");
a[2]=new BigInteger("119");
for(int i=3;i<=2000;i++)
{
a[i]=(a[i-1].add(a[i-2])).multiply(BigInteger.valueOf(5))
.add(BigInteger.valueOf(4)).subtract(a[i-3]);
}
}
}
参考文献
- icpc2017南宁H The Game of Life
- ACM 2017 南宁区域赛 Rake it in(对抗搜索)
|