这篇题解差点咕掉
将一个装备的两个属性连上边
对于树型联通块，只有最大的属性值不能被选
对于存在环的联通块，每个属性都可以被选
主流做法有两种：
(1):并查集
每次将一个装备的两个属性连到一个并查集
如果已经在一个并查集里说明是环
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#define rint register int
using namespace std;
const int maxn=1e6+5;
int fa[maxn],size[maxn];
bool cir[maxn];
int Find(int x){return fa[x]==x ? x : fa[x]=Find(fa[x]); }
int main(){
freopen("game.in","r",stdin);
freopen("game.out","w",stdout);
int n;scanf("%d",&n);
for(rint i=1;i<=n+1;i++) fa[i]=i,size[i]=1;
for(rint i=1;i<=n;i++){
int x,y;
scanf("%d%d",&x,&y);
if(Find(x)==Find(y)) cir[Find(x)]=1;
else{
cir[Find(x)]=cir[Find(x)]|cir[Find(y)];
size[Find(x)]+=size[Find(y)];
fa[Find(y)]=Find(x);
}
}
for(rint i=1;i<=n+1;i++){
if(!cir[Find(i)]){
if(size[Find(i)]==1) return printf("%d\n",i-1);
else size[Find(i)]--;
}
}
return 0;
}
(2):二分图
把两个属性跟这个装备连边，每次只能选一个属性就是匹配的过程
注意不能每次都memset一下vis数组，会起飞打个时间戳就行
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#define rint register int
using namespace std;
const int maxn=1e6+5;
int mat[maxn],vis[maxn],head[maxn],len;
int Time,ans;
struct Node{
int to,next;
}e[maxn<<1];
void Add(int x,int y){
e[++len].to=y;
e[len].next=head[x];
head[x]=len;
}
int Find(int u){
vis[u]=Time;
for(rint i=head[u];i;i=e[i].next){
int v=e[i].to;
if(vis[v]==Time) continue;
vis[v]=Time;
if(mat[v]==-1||Find(mat[v])){
mat[v]=u;
return 1;
}
}
return 0;
}
int main(){
freopen("game.in","r",stdin);
freopen("game.out","w",stdout);
memset(mat,-1,sizeof(mat));
int n;scanf("%d",&n);
for(rint i=1;i<=n;i++){
int x,y;scanf("%d%d",&x,&y);
Add(x+n,i);Add(y+n,i);
}
for(rint i=n+1;;i++){
Time=i;
if(!Find(i)) break;
ans++;
}
printf("%d\n",ans);
return 0;
}
非主流思路：
大力贪心，直接乱搞能过
约瑟夫问题
线性求解显然不能过，思考优化
我们这时可以发现m很小，因此不是每轮操作都需要取模
于是可以把每次加m的操作改成乘法，减少操作次数
时间复杂度：O(能过)
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#define rint register int
using namespace std;
int n,m;
int main(){
freopen("mayuri.in","r",stdin);
freopen("mayuri.out","w",stdout);
int T;scanf("%d",&T);
while(T--){
scanf("%d%d",&n,&m);
int now=0,die=1;
for(rint i=n-1;i>=1;i--){
if(n-i+1==m-1) break;
die=m%(n-i+1);
now=(die+now)%(n-i+1);
}
int len=n-m-1;
if(m==2) len++;
if(len<=0){
printf("%d\n",now+1);
continue;
}
int last,x,ren=m;
if(m==2) ren--;
while(len){
last=ren-now;
x=last/(m-1);
if(len>=x){
len-=x;
now+=x*m;
ren+=x;
}
else{
now+=len*m;
len=0;
}
if(len){
ren++;
now=(now+m)%(ren+1);
len--;
}
}
printf("%d\n",now+1);
}
return 0;
}
推柿子。
最后我们发现只关心x的平方，y的平方和x*y
线段树或者树状数组维护
当然线段树常数较大，需要卡常卡好久
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#define rint register int
using namespace std;
typedef long long ll;
const int maxn=1e6+5;
const int mod=20170927;
int a[maxn],b[maxn];
int A,B,AB,ans;
struct Node{
int l,r;
ll ma,mb,mul;
}t[maxn<<2];
void pushup(int rt){
t[rt].ma=(t[rt<<1].ma+t[rt<<1|1].ma)%mod;
t[rt].mb=(t[rt<<1].mb+t[rt<<1|1].mb)%mod;
t[rt].mul=(t[rt<<1].mul+t[rt<<1|1].mul)%mod;
}
void Build(int rt,int l,int r){
t[rt].l=l;t[rt].r=r;
if(l==r){
t[rt].ma=1LL*a[l]*a[l]%mod;
t[rt].mb=1LL*b[l]*b[l]%mod;
t[rt].mul=1LL*a[l]*b[l]%mod;
return;
}
int mid=l+r>>1;
Build(rt<<1,l,mid);
Build(rt<<1|1,mid+1,r);
pushup(rt);
}
void modify(int rt,int pos,int v1,int v2){
if(t[rt].l==t[rt].r){
t[rt].ma=1LL*v1*v1%mod;
t[rt].mb=1LL*v2*v2%mod;
t[rt].mul=1LL*v1*v2%mod;
return;
}
int mid=t[rt].l+t[rt].r>>1;
if(pos<=mid) modify(rt<<1,pos,v1,v2);
else modify(rt<<1|1,pos,v1,v2);
pushup(rt);
}
void query(int rt,int l,int r){
if(l==r) return;
if(l<=t[rt].l&&t[rt].r<=r)
return A=(A+t[rt].ma)%mod,B=(B+t[rt].mb)%mod,AB=(t[rt].mul+AB)%mod,void();
int mid=t[rt].l+t[rt].r>>1;
if(l<=mid) query(rt<<1,l,r);
if(r>mid) query(rt<<1|1,l,r);
}
int main(){
freopen("kurisu.in","r",stdin);
freopen("kurisu.out","w",stdout);
int n,m;
scanf("%d%d",&n,&m);
for(rint i=1;i<=n;i++) scanf("%d%d",&a[i],&b[i]);
Build(1,1,n);
int op,p,x,y;
for(rint i=1;i<=m;i++){
scanf("%d",&op);
if(op==1){
scanf("%d%d%d",&p,&x,&y);
modify(1,p,x,y);
}else{
A=0,B=0,AB=0;
scanf("%d%d",&x,&y);
query(1,x,y);
ans=(1LL*A*B%mod-1LL*AB*AB%mod+mod)%mod;
printf("%d\n",ans);
}
}
return 0;
}
单词积累：phoenix 凤凰
推荐补番：命运石之门
LCIS板子原来爷不会
翻了翻课件原来爷什么都不会
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#define rint register int
using namespace std;
const int maxn=5005;
int a[maxn],b[maxn],dp[maxn][maxn],pre[maxn][maxn];
void Print(int x,int y){
if(x==0) return;
Print(x-1,pre[x][y]);
if(dp[x][y]!=dp[x-1][pre[x][y]])
printf("%d ",b[y]);
}
int main(){
int n;scanf("%d",&n);
for(rint i=1;i<=n;i++) scanf("%d",&a[i]);
int m;scanf("%d",&m);
for(rint i=1;i<=m;i++) scanf("%d",&b[i]);
for(rint i=1;i<=n;i++){
int Max=0,k=0;
for(rint j=1;j<=m;j++){
dp[i][j]=dp[i-1][j];pre[i][j]=j;
if(a[i]>b[j]&&Max<dp[i-1][j])
Max=dp[i-1][j],k=j;
if(a[i]==b[j])
dp[i][j]=Max+1,pre[i][j]=k;
}
}
int ans=0;
for(rint i=1;i<=m;i++)
if(dp[n][i]>dp[n][ans]) ans=i;
printf("%d\n",dp[n][ans]);
Print(n,ans);
return 0;
}
原文：https://www.cnblogs.com/TheSure/p/13815010.html