不知道开头说点什么就给你劈个叉吧。

  • C - 开关问题

题意：http://poj.org/problem?id=1830
一开始拿深搜加状压刚果然超时了，，，看网上直接深搜都可以过怕是假的吧，，，有时间要再学一下计算复杂度了。
通过这个题复习了线代，高斯消元求解线性方程组。
use[1]表示开关1 relate[1][2]表示开关1对灯2是否有影响
u[1]*r[1][1]^u[2]*r[2][1]^u[3]*r[3][1]……^u[n]*r[n][1] = start[1]^end[1]
最后求出变元个数x，2^x即为答案。 

	//#include <bits/stdc++.h>
#include<map>
#include<set>
#include<queue>
#include<cmath>
#include<stack>
#include<ctime>
#include<cstdio>
#include<vector>
#include<string>
#include<sstream>
#include<cstdlib>
#include<cstring>
#include<cassert>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const int MAXN=1e5+10;
#define pi   acos(-1.0)
#define mod  1000000009
#define INF 0x3f3f3f3f3f
#define endll printf("\n")
#define s1(a) scanf("%d",&a)
#define s2(a,b) scanf("%d %d",&a,&b)
#define mem(a,b) memset(a,b,sizeof(a))
#define s3(a,b,c) scanf("%d %d %d",&a,&b,&c)
//高斯消元
int n;
int relate[30][30];
void input()
{
    s1(n);
    mem(relate,0);
    for(int i=0;i<n;s1(relate[i++][n]));
    for(int i=0;i<n;i++)
    {
        relate[i][i]=1;
        int x;s1(x);
        relate[i][n]^=x;





	}
    int I,J;
    while(s2(I,J)&&(I+J))
        relate[J-1][I-1]=1;
}
int guess(int n,int m)
{
    int i=0,j=0;//目前处理到哪一行
    int r;//找到j列第一个不为零的元素所在行
    while(i<n&&j<m)
    {
        //生成阶梯矩阵
        for(r=i;r<n;r++)
            if(relate[r][j]) break;
        if(r<n)
        {
            for(int k=0;k<=m;k++)
                swap(relate[r][k],relate[i][k]);
            //开始消元
            for(int k=i+1;k<n;k++)
            {
                if(!relate[k][j]) continue;
                for(int c=j;c<=m;c++)
                    relate[k][c]^=relate[i][c];
            }
            i++;
        }
        j++;
    }
    //计算最后自由变元个数
    for(int k=i;k<n;k++)
        if(relate[k][m]) return -1;
    return 1<<(n-i);
}
int main()
{
    int t;s1(t);
    while(t--)
    {
        input();
        int ans=guess(n,n);
        if(ans==-1) printf("Oh,it's impossible~!!\n");
        else printf("%d\n",ans);
    }
    return 0;
}

  • G - Tunnels 

天啊好不容易码好文我一手骚操作居然删了我哭了，，，，
再写一遍。。。
旅行商问题：
某点出发，要经过n个点，最后回到起点，求最短距离。
这个问题就是最短路的变形，只不过不要求回到起点，所以dp[i][0]（集合为空集的情况）初始化为0，而不是dis[i][起点]。
还有一点就是需要进行预处理，将隧道缩点，dis[i][j]代表 i隧道尾部到达j隧道头部的距离。
注意dp初始化，然后顺推就行，根据图理解状态转移。

AC代码： 
//#include <bits/stdc++.h>
#include<map>
#include<set>
#include<queue>
#include<cmath>
#include<stack>
#include<ctime>
#include<cstdio>
#include<vector>
#include<string>
#include<sstream>
#include<cstdlib>
#include<cstring>
#include<cassert>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const int MAXN=1e5+10;
#define pi    acos(-1.0)
#define INF 0x3f3f3f3f
#define mod   1000000009
#define endll printf("\n")
#define s1(a) scanf("%d",&a)
#define s2(a,b) scanf("%d %d",&a,&b)
#define mem(a,b) memset(a,b,sizeof(a))
#define s3(a,b,c) scanf("%d %d %d",&a,&b,&c)
int n,m;
char s[20][20];//存图
struct IN
{
    int a,b,c,d;
}tun[20];
int dis[20][20];//一个隧道尾到另一个隧道头的最短距离
int dp[20][1<<16];
int dx[4]={1,-1,0,0};
int dy[4]={0,0,-1,1};
vector<int>state[20][20];//起点编号
int ok(int x,int y)
{
    if(x<1||x>n||y<1||y>n)
        return 0;
    if(s[x][y]=='#')
        return 0;
    return 1;
}
void bfs(int x)//state编号
{
    int d[20][20];
    mem(d,-1);
    queue<int>q;
    q.push((tun[x].c-1)*n+(tun[x].d-1));
    d[tun[x].c][tun[x].d]=0;
    while(!q.empty())
    {
        int xx=q.front();q.pop();
        int yy=xx%n+1;
        xx=xx/n+1;
        if(state[xx][yy].size())
        {
            int len=state[xx][yy].size();
            for(int i=0;i<len;i++)
                dis[x][state[xx][yy][i]]=d[xx][yy];
        }
        for(int i=0;i<4;i++)
        {
            int nx=xx+dx[i],ny=yy+dy[i];
            if(!ok(nx,ny)||d[nx][ny]!=-1) continue;
            d[nx][ny]=d[xx][yy]+1;
            q.push((nx-1)*n+ny-1);
        }
    }
}
int main()
{
    while(~s2(n,m))
    {
        mem(dis,0x3f);
        for(int i=0;i<=n;i++)
        {
            for(int j=0;j<=n;j++)
                state[i][j].clear();
        }
        for(int i=1;i<=n;i++)
            scanf("%s",s[i]+1);
        for(int i=0;i<m;i++)
        {
            scanf("%d %d %d %d",&tun[i].a,&tun[i].b,&tun[i].c,&tun[i].d);
            state[tun[i].a][tun[i].b].push_back(i);
        }
        for(int i=0;i<m;i++)
            bfs(i);
        int all=(1<<m);
        for(int i=0;i<=m;i++)
        {
            for(int j=0;j<=all;j++)
            {
                dp[i][j]=(j==0?0:INF);//j代表此状态要走过的点
            }
        }
        //  d(0,{1,2,3})=min{C01+d(1,{2,3})，C02+d{2,{1,3}}，C03+d{3,{1,2}}}
        for(int s=1;s<all-1;s++)//枚举u的状态
        {
            for(int u=0;u<m;u++)
            {
                if(s&(1<<u)) continue;
                for(int v=0;v<m;v++)
                        if((s&(1<<v)))//保证v在u要走的集合中
                            dp[u][s]=min(dp[u][s],dp[v][s^(1<<v)]+dis[u][v]);
            }
        }
        int ans=INF;
        for(int i=0;i<m;i++)
            ans=min(ans,dp[i][(all-1)^(1<<i)]);
        printf("%d\n",ans==INF?-1:ans);
    }
    return 0;
}