T1
[TJOI2013] 攻击装置
题目描述
给定一个 01 矩阵，其中你可以在 0 的位置放置攻击装置。每一个攻击装置 \((x,y)\) 都可以按照“日”字攻击其周围的 \(8\) 个位置 \((x-1,y-2)\)，\((x-2,y-1)\)，\((x+1,y-2)\)，\((x+2,y-1)\)，\((x-1,y+2)\)，\((x-2,y+1)\)，\((x+1,y+2)\)，\((x+2,y+1)\)。
求在装置互不攻击的情况下，最多可以放置多少个装置。
输入格式
第一行一个整数 \(N\)，表示矩阵大小为 \(N \times N\)。
接下来 \(N\) 行每一行一个长度 \(N\) 的 01 串，表示矩阵。
输出格式
一个整数，表示在装置互不攻击的情况下最多可以放置多少个装置。
样例 #1
样例输入 #1
3
010
000
100
样例输出 #1
4
提示
对于 \(30\%\) 的数据，保证 \(N \le 50\)。
对于 \(100\%\) 的数据，保证 \(N \le 200\)。
这道题，很显然是两个"对象"之间的关系，我们可以想到二分图求最大独立集，然后如何连边呢，连边我们俩可以通过给点新加编号1~\(n^2\),然后8个方向,每个点只需考虑\((x-1,y+2)\)，\((x-2,y+1)\),\((x-1,y-2)\)，\((x-2,y-1)\)这四个方向,这算一个优化(当然你也可以不考虑),然后关键是遍历用匈牙利求时时不成立的点要忽略(考试时遗漏了,听取Wa声一片),如果你奇偶判断的话,答案不用除以2，如果不奇偶的话，答案要除以2，左右集合种类一样二分图匈牙利算法求的是双向边
点击查看代码
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N =505;
int n,a[N][N],match[N*N],g[N][N],head[N*N],cnt,ju[N][N];int vis[N*N];
int x[10]={0,-1,-2,-1,-2,1,2,1,2};
int y[10]={0,-2,-1,2,1,-2,-1,-2,-1};
struct Edge
{
int u,to,next;
}edge[N*N*2];
void add(int u,int v)
{
edge[++cnt].u=u;
edge[cnt].to=v;
edge[cnt].next=head[u];
head[u]=cnt;
}
bool dfs(int now,int id)
{
for(int i=head[now];i;i=edge[i].next)
// for(int i=1;i<=n;i++)
{
int to=edge[i].to;
if(to==now)continue;
// int to=i;
if(vis[to]!=id)
{
vis[to]=id;
if(!match[to]||dfs(match[to],id))
{
match[to]=now;
return true;
}
}
}
return false;
}
int tmp=0;
int xly()
{
int ans=0,now=0;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
{
if(!a[i][j])//&&(i+j)&1
{
++now;
if(dfs(ju[i][j],now))ans++;
}
}
return ans;
}
int main()
{
// freopen("attack.in","r",stdin);
// freopen("attack.out","w",stdout);
scanf("%d",&n);
int x1,tot=0;;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
scanf("%1d",&x1);
a[i][j]=x1;tot+=(!x1);
ju[i][j]=++tmp;
}
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
if(a[i][j])continue;
for(int k=1;k<=8;k++)
{
int yy=j+y[k];
int xx=i+x[k];
if(xx>0&&yy>0&&yy<=n&&xx<=n&&!a[xx][yy])
{
add(ju[i][j],ju[xx][yy]);
add(ju[xx][yy],ju[i][j]);
}
}
}
}
cout<<tot-xly()/2<<endl;//tot-xly()
return 0;
}
/*
3
010
000
100
*/
点击查看代码
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int mod=100;
int x,a[100000000];
ll qpow(ll a,ll b)
{
ll ans=1;
while(b)
{
if(b&1)ans=1ll*ans*a%mod;
b>>=1;
a=1ll*a*a%mod;
}
return ans;
}
int main()
{
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
freopen("number.in","r",stdin);
freopen("number.out","w",stdout);
cin>>x;
map <int,int> mp;
for(int j=1;;j++)
{
ll tmp=qpow(x,j);
cout<<tmp<<" ";
if(mp[tmp])
{
break;
}
mp[tmp]=1;
}
return 0;
}
点击查看代码
#include <bits/stdc++.h>
#define lid st[rt].l
#define rid st[rt].r
#define ll long long
using namespace std;
const int N=1e5+5;
int n,MIN;
struct ac
{
int d,v;
}a[N];
int main()
{
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
freopen("jog.in","r",stdin);
freopen("jog.out","w",stdout);
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i].d>>a[i].v;
}
int ans=0;
MIN=INT_MAX;
for(int i=n;i>=1;i--)
{
if(a[i].v<=MIN)
{
ans++;
MIN=a[i].v;
}
}
cout<<ans<<endl;
return 0;
}
/*
5
0 1
1 2
2 3
3 2
6 1
*/
点击查看代码
#include <bits/stdc++.h>
#define lid st[rt].l
#define rid st[rt].r
#define ll long long
using namespace std;
const int N=1e5+5;
int n,MAX,segtot,root[N];
struct ac
{
int d,v;
}a[N];
struct tree
{
int l,r,cnt,lz;
}st[N*35];
void pushup(int rt)
{
st[rt].cnt=st[lid].cnt+st[rid].cnt;
}
void pushdown(int rt)
{
if(st[rt].lz)
{
st[rt].lz=0;
st[lid].lz=st[rid].lz=1;
st[lid].cnt=st[rid].cnt=0;
}
}
void update(int &rt,int l,int r,int pos,int val)
{
if(!rt)rt=++segtot;
if(l==r)
{
st[rt].cnt+=val;
return;
}
int mid=(l+r)>>1;
if(pos<=mid)update(lid,l,mid,pos,val);
else update(rid,mid+1,r,pos,val);
pushup(rt);
}
void del(int rt,int l,int r,int L,int R)
{
if(L>R)return;
if(!rt)return;
if(L<=l&&r<=R)
{
st[rt].cnt=0;st[rt].lz=1;
return;
}
pushdown(rt);
int mid=(l+r)>>1;
if(L<=mid)del(lid,l,mid,L,R);
if(R>mid)del(rid,mid+1,r,L,R);
pushup(rt);
}
int query(int rt,int l,int r,int L,int R)
{
if(!rt)return 0;
if(L<=l&&r<=R)
{
return st[rt].cnt;
}
int mid=(l+r)>>1;
int ans=0;
if(L<=mid)ans+=query(lid,l,mid,L,R);
if(R>mid)ans+=query(rid,mid+1,r,L,R);
return ans;
}
int segtree(int ra,int rb)
{
if(!ra)return rb;
if(!rb)return ra;
st[ra].cnt+=st[rb].cnt;
st[ra].l=segtree(st[ra].l,st[rb].l);
st[ra].r=segtree(st[rb].r,st[rb].r);
return ra;
}
int main()
{
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
freopen("jog.in","r",stdin);
freopen("jog.out","w",stdout);
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i].d>>a[i].v;
MAX=max(MAX,a[i].v);
}
update(root[n],1,MAX,a[n].v,1);
for(int i=n-1;i>=1;i--)
{
if(query(root[n],1,MAX,1,a[i].v-1))
{
continue;
}else
{
update(root[i],1,MAX,a[i].v,1);
root[n]=segtree(root[n],root[i]);
}
}
cout<<query(root[n],1,MAX,1,MAX)<<endl;
return 0;
}
/*
5
0 1
1 2
2 3
3 2
6 1
*/
点击查看代码
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N =5e4+5;
int a,b,p;
bool ispri[N];int prim[N],tot;
void get(int n)
{
ispri[1]=1;
for(int i=2;i<=n;i++)
{
if(!ispri[i])
{
prim[++tot]=i;
}
for(int j=1;j<=tot;j++)
{
if(prim[j]*i>n)break;
ispri[prim[j]*i]=1;
if(i%prim[j]==0)break;
}
}
}
set <int> zu[N];
vector <int> he[N];bool vis[N];
int pos,unok,ans;
void fen(int x)
{
bool flag=0;
for(int i=pos;i<=tot;i++)
{
if(x<prim[i])break;
if(x%prim[i]==0&&prim[i]>=p)
{
flag=1;
zu[prim[i]].insert(x);
he[x].push_back(prim[i]);
}
}
if(!flag)
{
vis[x]=1;
ans++;
// cout<<he[x].size()<<endl;
}
}
int havn[N];
int main()
{
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
freopen("merge.in","r",stdin);
freopen("merge.out","w",stdout);
cin>>a>>b>>p;
get(b);
pos=lower_bound(prim+1,prim+tot,p)-prim;
for(int i=a;i<=b;i++)
{
fen(i);
}
int now=0;
for(int su=a;su<=b;su++)
{
int zuhao=INT_MAX;bool is=0;
for(auto j:he[su])
{
// cout<<j<<endl;
if(havn[j])
{
zuhao=min(zuhao,havn[j]);
is=1;
}
}
if(!is)
{
now++;
for(auto j:he[su])havn[j]=now;
}else
for(auto j:he[su])havn[j]=zuhao;
}
// for(int i=pos;i<=tot;i++)
// {
// cout<<prim[i]<<" "<<havn[prim[i]]<<endl;
// }
now=0;
memset(vis,0,sizeof(vis));
for(int i=pos;i<=tot;i++)
{
int su=prim[i];
if(!vis[havn[su]])
{
vis[havn[su]]=1;
now++;
}
}
cout<<ans+now;
return 0;
}
/*
10 20 3
*/