唯一一次提早下班
T1：蓝题，但黄题（有人没文件读写）
//100pts
#include<bits/stdc++.h>
using namespace std;
long long T,n,m,ak,ans[10005][7],cnt,xl[5],yl[5],flag=0;
char a[105][105];
void work(int xa,int ya,int xb,int yb,int xc,int yc) {
ak++;
ans[ak][1]=xa,ans[ak][2]=ya,ans[ak][3]=xb,ans[ak][4]=yb,ans[ak][5]=xc,ans[ak][6]=yc;
if(a[xa][ya]=='0') a[xa][ya]='1';
else a[xa][ya]='0';
if(a[xb][yb]=='0') a[xb][yb]='1';
else a[xb][yb]='0';
if(a[xc][yc]=='0') a[xc][yc]='1';
else a[xc][yc]='0';
}
void op(int x,int y)
{
if(x==n-1&&y==m-1)
{
work(x,y,x+1,y,x,y+1);
work(x,y,x+1,y,x+1,y+1);
work(x,y,x,y+1,x+1,y+1);
return ;
}
if(x==n-1&&y==m)
{
work(x,y,x,y-1,x+1,y);
work(x,y,x,y-1,x+1,y-1);
work(x,y,x+1,y,x+1,y-1);
return ;
}
if(x==n&&y==m-1)
{
work(x,y,x-1,y,x,y+1);
work(x,y,x-1,y,x-1,y+1);
work(x,y,x,y+1,x-1,y+1);
return ;
}
if(x==n&&y==m)
{
work(x,y,x-1,y,x,y-1);
work(x,y,x-1,y,x-1,y-1);
work(x,y,x,y-1,x-1,y-1);
return ;
}
}
int main() {
freopen("bulb.in","r",stdin);
freopen("bulb.out","w",stdout);
cin>>T;
while(T--) {
ak=0;
scanf("%lld%lld",&n,&m);
for(int i=1; i<=n; i++) {
for(int j=1; j<=m; j++) {
cin>>a[i][j];
}
}
for(int i=1; i<=n-2; i++) {
for(int j=1; j<=m; j++) {
if(a[i][j]=='0') continue;
if(a[i][j]=='1') {
if(j!=m) {
if(a[i][j+1]!='1') work(i,j,i+1,j,i+1,j+1);
else work(i,j,i,j+1,i+1,j);
} else work(i,j,i+1,j,i+1,j-1);
}
}
}
for(int j=1; j<=m-2; j++) {
for(int i=n-1; i<=n; i++) {
if(a[i][j]=='0') continue;
if(a[i][j]=='1') {
if(i==n-1)
{
if(a[i+1][j]=='1') work(i,j,i+1,j,i,j+1);
else work(i,j,i,j+1,i+1,j+1);
}
else work(i,j,i,j+1,i-1,j+1);
}
}
}
cnt=0;
for(int i=n-1;i<=n;i++)
{
for(int j=m-1;j<=m;j++)
{
if(a[i][j]=='1')
{
cnt++;
xl[cnt]=i;
yl[cnt]=j;
}
}
}
if(cnt==3)
{
work(xl[1],yl[1],xl[2],yl[2],xl[3],yl[3]);
}
flag=0;
if(cnt==2)
{
for(int i=n-1;i<=n;i++)
{
for(int j=m-1;j<=m;j++)
{
if(a[i][j]=='0')
{
work(xl[1],yl[1],xl[2],yl[2],i,j);
op(i,j);
flag=1;
break;
}
}
if(flag==1) break;
}
}
if(cnt==1)
{
op(xl[1],yl[1]);
}
if(cnt==4)
{
work(xl[1],yl[1],xl[2],yl[2],xl[3],yl[3]);
op(xl[4],yl[4]);
}
printf("%lld\n",ak);
for(int i=1;i<=ak;i++)
{
for(int j=1;j<=6;j++) printf("%lld ",ans[i][j]);
cout<<endl;
}
}
return 0;
}
T2：
n<=1e5,但k很少
考虑将n映射到k上，则可以状压解决（可以发现答案不会更优）
考虑随机，答案对应的k个值映射到不同的k的概率为“k!/k^k”约为24/256
多随机几次就好了
#include<bits/stdc++.h>
using namespace std;
long long st;
int n,k,id[10005],uu,vv,ans=114514,tt[10005],sum,num,step=75,kl[10005],v;
int dp[10001][32];
vector<int> G[10005];
mt19937 rd(time(0));
void dfs(int x,int f) {
for(int i=0;i<G[x].size();i++)
{
if(G[x][i]!=f) dfs(G[x][i],x);
}
for(int i=1;i<st;i++) dp[x][i]=114514;
// dp[x][0]=1;
dp[x][1<<(kl[x]-1)]=1;
for(int i=0;i<G[x].size();i++)
{
v=G[x][i];
if(v!=f)
{
for(int j=0;j<st;j++)
{
for(int h=0;h<st;h++)
{
dp[x][j|h]=min(dp[x][j|h],dp[x][j]+dp[v][h]);
}
}
ans=min(ans,dp[x][st-1]);
}
}
return ;
}
int main() {
freopen("insect.in","r",stdin);
freopen("insect.out","w",stdout);
cin>>n>>k;
for(int i=1; i<=n; i++) {
scanf("%d",&id[i]);
}
for(int i=1; i<=n-1; i++) {
scanf("%d%d",&uu,&vv);
G[uu].push_back(vv);
G[vv].push_back(uu);
}
st=1<<k;
while(step--)
{
for(int i=1;i<=n;i++)
{
tt[i]=(rd()%k+k)%k+1;
}
for(int i=1;i<=n;i++)
{
kl[i]=tt[id[i]];
}
dfs(1,0);
}
cout<<ans;
return 0;
}
T3
发现一定有解，又发现如果有一个点跟两个以上讨厌的点在同一个集合，则另一集合讨厌的最多一个
则交换当前点位置一定更优
交换完再遍历考虑有关联的点
//30pts
#include<bits/stdc++.h>
using namespace std;
long long n,m,aa,bb,st,flag,cnt,f[300005];
vector<int> G[300005];
void work(int x)
{
cnt=0;
for(int i=0;i<G[x].size();i++) if(f[x]==f[G[x][i]]) cnt++;
if(cnt>=2)
{
f[x]=f[x]^1;
for(int i=0;i<G[x].size();i++) work(G[x][i]);
}
}
int main() {
// freopen("horse.in","r",stdin);
// freopen("horse.out","w",stdout);
cin>>n>>m;
for(int i=1;i<=m;i++)
{
scanf("%lld%lld",&aa,&bb);
G[aa].push_back(bb);
G[bb].push_back(aa);
}
for(int i=1;i<=n;i++)
{
work(i);
}
for(int i=1;i<=n;i++) cout<<f[i];
return 0;
}
T4
容斥，都能想到，ans=sigma（0~n）（f[i]jc[n-i](-1)^i）
(选定碰到i个障碍，剩下随便选)
考虑如何计算f[i]（碰到i个障碍的方案数）
将每一个a[i]和b[i]的值连边，则图必定为一些环加一些链
则方案为一个端点只能属于一条边的方案数
考虑将每两个点中间加一个点，就转化为点匹配
n个点匹配k个，相当于从n个点中取出k个，不能相邻
则答案为C(n-k,k)
再来考虑环，若不选（1，n），则答案跟链一样；选（1，n），则转化为剩下链选k-1个
答案为C(n-k,k)+C(n-2-(k-1)=n-k-1,k-1)
单独处理完后背包合并就好了，把每一个环的不同数量的贡献拆开，共n个（共n个点），容量为n
“`cpp
</h3>
#include
using namespace std;
const long long mod=1e9+7;
int op=1,vv;
long long hf[3005][3005],f[3005][3005];
long long n,a[3005],b[3005],st,ans,jc[6005],ny[6005],fl=-1,ls,id,cnt,vis[3005],flag,hsum[3005],u[6005],v[6005],head[3005],nex[6005];
void add(int xx,int yy) {
op++;
u[op]=xx,v[op]=yy;
nex[op]=head[u[op]];
head[u[op]]=op;
}
long long ksm(long long aa,long long bb ) {
ls=1;
while(bb>0) {
if(bb%2<span class="text-highlighted-inline" style="background-color: #fffd38;">1) {
ls=(ls<em>aa)%mod;
}
bb/=2;
aa=(aa</em>aa)%mod;
}
return ls;
}
void dfs(int x,int ed) {
vis[x]=cnt;
for(int i=head[x]; i!=0; i=nex[i]) {
if(vis[v[i]]</span>0) {
dfs(v[i],i);
hsum[cnt]++;
} else {
if(vis[v[i]]!=0&&i!=(ed^1)&&v[i]!=x) {
flag=1;
return ;
}
}
}
}
long long C(int aa,int bb) {
if(bb<span class="text-highlighted-inline" style="background-color: #fffd38;">0) return 1;
if(aa<bb) return 0;
else return ((jc[aa]<em>ny[aa-bb]%mod)</em>ny[bb]%mod)%mod;
}
void work() {</span>
<pre><code>cnt=0;
for(int i=1; i<=n; i++) {
if(vis[i]==0) {
flag=0;
cnt++;
hsum[cnt]=1;
vis[i]=cnt;
dfs(i,0);
hf[cnt][0]=1;
// cout<<flag<<endl;
if(flag==0) {
for(int j=1; j<=hsum[cnt]; j++) {
hf[cnt][j]=C(2*hsum[cnt]-j,j);
hf[cnt][j]%=mod;
}
} else {
for(int j=1; j<=hsum[cnt]; j++) {
hf[cnt][j]=C(2*hsum[cnt]-j,j)+C(2*hsum[cnt]-j-1,j-1);
hf[cnt][j]%=mod;
}
}
}
}
</code></pre>
// for(int i=1;i<=cnt;i++)
// {
// cout<<i<<": "<<hsum[i]<<endl;;
// for(int j=1;j<=hsum[i];j++) cout<<" "<<hf[i][j]<<" ";
// cout<<endl;
// }
f[0][0]=1;
for(int i=1; i=1; h–) {
f[i][h]=f[i-1][h];
for(int j=hsum[i]; j>=1; j–) {
if(h>=j) {
f[i][h]+=f[i-1][h-j]*hf[i][j];
f[i][h]%=mod;
}
}
}
}
}
int main() {
// freopen("game.in","r",stdin);
// freopen("game.out","w",stdout);
cin>>n;
for(int i=1; i<=n; i++) scanf("%lld",&a[i]);
for(int i=1; i<=n; i++) scanf("%lld",&b[i]);
for(int i=1; i<=n; i++) {
add(a[i],b[i]);
add(b[i],a[i]);
}
jc[0]=1;
for(int i=1; i=1; i–) ny[i]=(ny[i+1]<em>(i+1))%mod;
ny[0]=1;
work();
fl=1;
// for(int i=0;i<=n;i++)
// {
// cout<<f[cnt][i]<<endl;
// }
for(int i=0; i<=n; i++) {
ans=(ans+mod+(fl</em>(f[cnt][i]%mod*jc[n-i]%mod))%mod)%mod;
fl=-fl;
}
cout<<ans;
return 0;
}
“`n^n