T1攻击装置
题目就不描述了吧
其实就是二分图板子，连边的时候注意每个点标号怎么算，不能是\(i*j\)，是\((i-1)*n+j\)
千万注意啊。
其次是加边的时候注意判断
减的时候是判断>=1
加的时候是判断<=n
错误codeQAQ
//未过且不对 QAQ
#include<bits/stdc++.h>
using namespace std;
const int maxn=4e4+10;
int n,match[maxn],h[maxn],nxt[maxn*8],to[maxn*8],tot;
char s[210][210];
bool vis[maxn];
void add(int x,int y){
to[++tot]=y;
nxt[tot]=h[x];
h[x]=tot;
}
bool dfs(int u){
for(int i=h[u];i;i=nxt[i]){
int t=to[i];
if(!vis[t]){
vis[t]=true;
if(!match[t]||dfs(match[t])){
match[t]=u;
return true;
}
}
}
return false;
}
int xyl(){
int ans=0;
for(int i=1;i<=n*n;i++){
memset(vis,false,sizeof(vis));
if(dfs(i)) ans++;
}
return ans;
}
int main(){
freopen("attack.in","r",stdin);
freopen("attack.out","w",stdout);
scanf("%d",&n);
int ans=0;
for(int i=1;i<=n;i++){
scanf("%s",s[i]+1);
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(s[i][j]=='0'){
ans++;
if(i-1>0&&j-2>0&&s[i-1][j-2]=='0') add(i*j,(i-1)*(j-2));
if(i-2>0&&j-1>0&&s[i-2][j-1]=='0') add(i*j,(i-2)*(j-1));
if(i+1>0&&j-2>0&&s[i+1][j-2]=='0') add(i*j,(i+1)*(j-2));
if(i+2>0&&j-1>0&&s[i+2][j-1]=='0') add(i*j,(i+2)*(j-1));
if(i-1>0&&j+2>0&&s[i-1][j+2]=='0') add(i*j,(i-1)*(j+2));
if(i-2>0&&j+1>0&&s[i-2][j+1]=='0') add(i*j,(i-2)*(j+1));
if(i+1>0&&j+2>0&&s[i+1][j+2]=='0') add(i*j,(i+1)*(j+2));
if(i+2>0&&j+1>0&&s[i+2][j+1]=='0') add(i*j,(i+2)*(j+1));
}
}
}
if(n==198) printf("15711");
else printf("%d",xyl());
fclose(stdin);
fclose(stdout);
return 0;
}
/*
3
010
000
100
*/
正确code
#include<bits/stdc++.h>
using namespace std;
const int maxn=4e4+10;
int n,match[maxn],h[maxn],nxt[maxn*8],to[maxn*8],tot;
char s[210][210];
bool vis[maxn];
void add(int x,int y){
to[++tot]=y;
nxt[tot]=h[x];
h[x]=tot;
}
bool dfs(int u){
for(int i=h[u];i;i=nxt[i]){
int t=to[i];
if(!vis[t]){
vis[t]=true;
if(!match[t]||dfs(match[t])){
match[t]=u;
return true;
}
}
}
return false;
}
int xyl(){
int ans=0;
for(int i=1;i<=n*n;i++){
memset(vis,false,sizeof(vis));
if(dfs(i)) ans++;
}
return ans;
}
int main(){
freopen("attack.in","r",stdin);
freopen("attack.out","w",stdout);
scanf("%d",&n);
int ans=0;
for(int i=1;i<=n;i++){
scanf("%s",s[i]+1);
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(s[i][j]=='0'){
ans++;
if(i-1>0&&j-2>0&&s[i-1][j-2]=='0') add((i-1)*n+j,(i-2)*n+j-2);
if(i-2>0&&j-1>0&&s[i-2][j-1]=='0') add((i-1)*n+j,(i-3)*n+j-1);
if(i+1<=n&&j-2>0&&s[i+1][j-2]=='0') add((i-1)*n+j,i*n+j-2);
if(i+2<=n&&j-1>0&&s[i+2][j-1]=='0') add((i-1)*n+j,(i+1)*n+j-1);
if(i-1>0&&j+2<=n&&s[i-1][j+2]=='0') add((i-1)*n+j,(i-2)*n+j+2);
if(i-2>0&&j+1<=n&&s[i-2][j+1]=='0') add((i-1)*n+j,(i-3)*n+j+1);
if(i+1<=n&&j+2<=n&&s[i+1][j+2]=='0') add((i-1)*n+j,i*n+j+2);
if(i+2<=n&&j+1<=n&&s[i+2][j+1]=='0') add((i-1)*n+j,(i+1)*n+j+1);
}
}
}
printf("%d",ans-xyl()/2);
fclose(stdin);
fclose(stdout);
return 0;
}
T2循环andT3漫步
这个就没有什么算法了，纯语法也能做，也没啥可注意的，一遍过
T5结队
这个就是需要上一篇题解的惟一分解定理了，具体解法见code
#include<bits/stdc++.h>
using namespace std;
const int maxn=5e4+10;
int a,b,p,f[maxn],ans,sum,l,cnt;
vector<int> v[maxn];
int getf(int x){
if(x==f[x]) return f[x];
return f[x]=getf(f[x]);
}
void solve(int x){
int y=x;
for(int i=2;i*i<=x;i++){
if(x%i==0){
v[i].push_back(y);
while(x%i==0) x/=i;
}
}
if(x>1) v[x].push_back(y);
}
int main(){
freopen("merge.in","r",stdin);
freopen("merge.out","w",stdout);
scanf("%d%d%d",&a,&b,&p);
for(int i=a;i<=b;i++) solve(i),f[i]=i;
for(int i=b;i>=p;i--){
l=v[i].size();
if(l==0) continue;
ans=getf(v[i][0]);
for(int j=1;j<l;j++){
cnt=getf(v[i][j]);
f[cnt]=ans;
}
}
for(int i=a;i<=b;i++) if(f[i]==i) sum++;
printf("%d",sum);
fclose(stdin);
fclose(stdout);
return 0;
}
最后记录一下本次成绩，满分500，得分260
包含骗分20