一本通刷题

一本通
队列part
1
http://ybt.ssoier.cn:8088/problem_show.php?pid=1332
队列先进先出

点击查看代码 
#include
#define rep(i,l,r) for(int i=int(l);i=int(l);i--)
#define repg(i,l,r) for(i=int(l);i=int(l);i--)
#define rept(i,t) for(int i=int(h[t]);~i;i=ne[i])
#define reph(i,t,h) for(int i=int(h[t]);~i;i=ne[i])
#define x first
#define y second
#define pb push_back
#define pf push_front
#define ppb pop_back
#define ppf pop_front
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long long ll;
typedef unsigned long long lll;
typedef pair PII;
typedef pair PDD;
const int INF=0x3f3f3f3f,mod=1e9+7;
const ll INFF=1e18;
const double eps=1e-14;
mt19937 mrand(random_device{}());
template ostream& operator <<(ostream& out, const pair &p) {
    return out << "(" << p.x << " " << p.y << ")";
}
template ostream& operator <<(ostream& out, const vector &v) {
    rep(i, 0, sz(v)) {
        if(i) out << " ";
        out << v[i];
    }
    return out;
}
int rnd(int x){return mrand()%x;}
ll qmi(ll a,ll b){ll res=1;a%=mod;while(b){if(b&1)res=res*a%mod;a=a*a%mod;b>>=1;}return res;}
ll qmul(ll a,ll b){ll res=0;a%=mod;while(b){if(b&1) res=(res+a)%mod;a=(a+a)%mod;b>>=1;} return res;}
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
/*ll read()
{
    ll x=0,f=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9')x=x*10+(c-'0'),c=getchar();
    return f*x;
}*/
//#include 
//#include 
//#include 
//#include 
//#include 
//using namespace std;
//int main()
//{
//    int ok = 0;
//    int n = 50;
//    for (int i = 1; i <= n; ++i)
//    {
//        system("make.exe > make.txt");
//        system("std.exe < make.txt > std.txt");
//        double begin = clock();
//        system("baoli.exe < make.txt > baoli.txt");
//        double end = clock();
//
//        double t = (end - begin);
//        if (system("fc std.txt baoli.txt"))
//        {
//            printf("测试点#%d Wrong Answer\n", i);
//        }
//        else if (t > 1000) //1秒
//        {
//            printf("测试点#%d Time Limited Exceeded 用时 %.0lfms\n", i, t);
//        }
//        else
//        {
//            printf("测试点#%d Accepted 用时%.0lfms\n", i, t);
//            ok++; //AC数量+1
//        }
//    }
//    printf("\n");
//    double res = 100.0 * ok / n;
//    printf("共 %d 组测试数据，AC数据 %d 组。 得分%.1lf。", n, ok, res);
//
//    Sleep(1000); //休眠1秒，为了节约对拍次数。
//}
inline int read()
{
    int x=0;
    char ch;
    bool fx=false;
    do ch=getchar();while(~ch&&ch!='-'&&(ch<48||ch>57));
    if(ch=='-')fx=true,ch=getchar();
    for(;ch>47&&ch<58;ch=getchar())
        x=(x<<1)+(x<<3)+(ch^48);
    return fx?-x:x;
}


int main()
{
#ifdef my_test
 	freopen(".in","r",stdin);
    freopen(".out","w",stdout);
#endif
#ifdef my_dp
	while(1)
	{
		system("data.exe > in.txt");
		system("brute.exe < in.txt > brute.txt");
		system("std.exe < in.txt > std.txt");
		if(system("fc std.txt brute.txt"))
			break;
	}
#endif
#ifdef my_dp2
    while (1) //一直循环，直到找到不一样的数据
    {
        system("data.exe");
        system("baoli.exe");
        system("std.exe");
        if (system("fc std.txt baoli.txt")) //当 fc 返回1时，说明这时数据不一样
            break;                          //不一样就跳出循环
    }
#endif
	clock_t start,end;
    start=clock();
    int n,m,t;n=read(),m=read();t=read();
	queue q1,q2; 
	rep(i,1,n+1) q1.push(i);
	rep(i,1,m+1) q2.push(i);
	rep(i,1,t+1)
	{
		printf("%d %d\n",q1.front(),q2.front());
		q1.push(q1.front()),q2.push(q2.front());	
		q1.pop(),q2.pop();
	} 
    end=clock();
//    printf("%lfms\n",(double)(end-start)/CLOCKS_PER_SEC*1000);
    return 0;
}
2

http://ybt.ssoier.cn:8088/problem_show.php?pid=1333

对于数列里的每一个数都会出现，然后每次从中取一个小的进入，成功就pop。最后把新的成功放入到两个队列里。这一次的一定比上一次的大

点击查看代码 
#include
#define rep(i,l,r) for(int i=int(l);i=int(l);i--)
#define repg(i,l,r) for(i=int(l);i=int(l);i--)
#define rept(i,t) for(int i=int(h[t]);~i;i=ne[i])
#define reph(i,t,h) for(int i=int(h[t]);~i;i=ne[i])
#define x first
#define y second
#define pb push_back
#define pf push_front
#define ppb pop_back
#define ppf pop_front
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long long ll;
typedef unsigned long long lll;
typedef pair PII;
typedef pair PDD;
const int INF=0x3f3f3f3f,mod=1e9+7;
const ll INFF=1e18;
const double eps=1e-14;
mt19937 mrand(random_device{}());
template ostream& operator <<(ostream& out, const pair &p) {
    return out << "(" << p.x << " " << p.y << ")";
}
template ostream& operator <<(ostream& out, const vector &v) {
    rep(i, 0, sz(v)) {
        if(i) out << " ";
        out << v[i];
    }
    return out;
}
int rnd(int x){return mrand()%x;}
ll qmi(ll a,ll b){ll res=1;a%=mod;while(b){if(b&1)res=res*a%mod;a=a*a%mod;b>>=1;}return res;}
ll qmul(ll a,ll b){ll res=0;a%=mod;while(b){if(b&1) res=(res+a)%mod;a=(a+a)%mod;b>>=1;} return res;}
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
/*ll read()
{
    ll x=0,f=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9')x=x*10+(c-'0'),c=getchar();
    return f*x;
}*/
//#include 
//#include 
//#include 
//#include 
//#include 
//using namespace std;
//int main()
//{
//    int ok = 0;
//    int n = 50;
//    for (int i = 1; i <= n; ++i)
//    {
//        system("make.exe > make.txt");
//        system("std.exe < make.txt > std.txt");
//        double begin = clock();
//        system("baoli.exe < make.txt > baoli.txt");
//        double end = clock();
//
//        double t = (end - begin);
//        if (system("fc std.txt baoli.txt"))
//        {
//            printf("测试点#%d Wrong Answer\n", i);
//        }
//        else if (t > 1000) //1秒
//        {
//            printf("测试点#%d Time Limited Exceeded 用时 %.0lfms\n", i, t);
//        }
//        else
//        {
//            printf("测试点#%d Accepted 用时%.0lfms\n", i, t);
//            ok++; //AC数量+1
//        }
//    }
//    printf("\n");
//    double res = 100.0 * ok / n;
//    printf("共 %d 组测试数据，AC数据 %d 组。 得分%.1lf。", n, ok, res);
//
//    Sleep(1000); //休眠1秒，为了节约对拍次数。
//}
inline int read()
{
    int x=0;
    char ch;
    bool fx=false;
    do ch=getchar();while(~ch&&ch!='-'&&(ch<48||ch>57));
    if(ch=='-')fx=true,ch=getchar();
    for(;ch>47&&ch<58;ch=getchar())
        x=(x<<1)+(x<<3)+(ch^48);
    return fx?-x:x;
}


int main()
{
#ifdef my_test
 	freopen(".in","r",stdin);
    freopen(".out","w",stdout);
#endif
#ifdef my_dp
	while(1)
	{
		system("data.exe > in.txt");
		system("brute.exe < in.txt > brute.txt");
		system("std.exe < in.txt > std.txt");
		if(system("fc std.txt brute.txt"))
			break;
	}
#endif
#ifdef my_dp2
    while (1) //一直循环，直到找到不一样的数据
    {
        system("data.exe");
        system("baoli.exe");
        system("std.exe");
        if (system("fc std.txt baoli.txt")) //当 fc 返回1时，说明这时数据不一样
            break;                          //不一样就跳出循环
    }
#endif
	clock_t start,end;
    start=clock();
	int a,n;
	while(~scanf("%d%d",&a,&n))
	{
		int ans=0;
		queue q1,q2,q; 
		q1.push(a),q2.push(a);
		rep(i,1,n)
		{
			int x=q1.front()*2+1,y=q2.front()*3+1; 
			if(xy)ans=y,q2.pop(); 
			else ans=x,q1.pop(),q2.pop();
			q1.push(ans),q2.push(ans); //每个数都会出现，所以二者的构成是一样的，只是有的剩余多，有的剩余少 
		}
		printf("%d\n",ans);
	}
    end=clock();
//    printf("%lfms\n",(double)(end-start)/CLOCKS_PER_SEC*1000);
    return 0;
}
3

http://ybt.ssoier.cn:8088/problem_show.php?pid=1334

约瑟夫环的队列写法，每次pop，push，只有在m的时候不push。实现对其的循环和去m

点击查看代码 
#include
#define rep(i,l,r) for(int i=int(l);i=int(l);i--)
#define repg(i,l,r) for(i=int(l);i=int(l);i--)
#define rept(i,t) for(int i=int(h[t]);~i;i=ne[i])
#define reph(i,t,h) for(int i=int(h[t]);~i;i=ne[i])
#define x first
#define y second
#define pb push_back
#define pf push_front
#define ppb pop_back
#define ppf pop_front
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long long ll;
typedef unsigned long long lll;
typedef pair PII;
typedef pair PDD;
const int INF=0x3f3f3f3f,mod=1e9+7;
const ll INFF=1e18;
const double eps=1e-14;
mt19937 mrand(random_device{}());
template ostream& operator <<(ostream& out, const pair &p) {
    return out << "(" << p.x << " " << p.y << ")";
}
template ostream& operator <<(ostream& out, const vector &v) {
    rep(i, 0, sz(v)) {
        if(i) out << " ";
        out << v[i];
    }
    return out;
}
int rnd(int x){return mrand()%x;}
ll qmi(ll a,ll b){ll res=1;a%=mod;while(b){if(b&1)res=res*a%mod;a=a*a%mod;b>>=1;}return res;}
ll qmul(ll a,ll b){ll res=0;a%=mod;while(b){if(b&1) res=(res+a)%mod;a=(a+a)%mod;b>>=1;} return res;}
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
/*ll read()
{
    ll x=0,f=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9')x=x*10+(c-'0'),c=getchar();
    return f*x;
}*/
//#include 
//#include 
//#include 
//#include 
//#include 
//using namespace std;
//int main()
//{
//    int ok = 0;
//    int n = 50;
//    for (int i = 1; i <= n; ++i)
//    {
//        system("make.exe > make.txt");
//        system("std.exe < make.txt > std.txt");
//        double begin = clock();
//        system("baoli.exe < make.txt > baoli.txt");
//        double end = clock();
//
//        double t = (end - begin);
//        if (system("fc std.txt baoli.txt"))
//        {
//            printf("测试点#%d Wrong Answer\n", i);
//        }
//        else if (t > 1000) //1秒
//        {
//            printf("测试点#%d Time Limited Exceeded 用时 %.0lfms\n", i, t);
//        }
//        else
//        {
//            printf("测试点#%d Accepted 用时%.0lfms\n", i, t);
//            ok++; //AC数量+1
//        }
//    }
//    printf("\n");
//    double res = 100.0 * ok / n;
//    printf("共 %d 组测试数据，AC数据 %d 组。 得分%.1lf。", n, ok, res);
//
//    Sleep(1000); //休眠1秒，为了节约对拍次数。
//}
inline int read()
{
    int x=0;
    char ch;
    bool fx=false;
    do ch=getchar();while(~ch&&ch!='-'&&(ch<48||ch>57));
    if(ch=='-')fx=true,ch=getchar();
    for(;ch>47&&ch<58;ch=getchar())
        x=(x<<1)+(x<<3)+(ch^48);
    return fx?-x:x;
}


int main()
{
#ifdef my_test
 	freopen(".in","r",stdin);
    freopen(".out","w",stdout);
#endif
#ifdef my_dp
	while(1)
	{
		system("data.exe > in.txt");
		system("brute.exe < in.txt > brute.txt");
		system("std.exe < in.txt > std.txt");
		if(system("fc std.txt brute.txt"))
			break;
	}
#endif
#ifdef my_dp2
    while (1) //一直循环，直到找到不一样的数据
    {
        system("data.exe");
        system("baoli.exe");
        system("std.exe");
        if (system("fc std.txt baoli.txt")) //当 fc 返回1时，说明这时数据不一样
            break;                          //不一样就跳出循环
    }
#endif
	clock_t start,end;
    start=clock();
	int n,m;n=read(),m=read();
	queue q;
	rep(i,1,n+1) q.push(i);
	int cnt=0;
	while(q.size())
	{
		cnt++;
		int tmp=q.front();
		if(cnt==m) cnt=0,printf("%d ",tmp);
		else q.push(tmp);
		q.pop();
	}
    end=clock();
//    printf("%lfms\n",(double)(end-start)/CLOCKS_PER_SEC*1000);
    return 0;
}

http://ybt.ssoier.cn:8088/problem_show.php?pid=1335

bfs连通块

点击查看代码 
#include
#define rep(i,l,r) for(int i=int(l);i=int(l);i--)
#define repg(i,l,r) for(i=int(l);i=int(l);i--)
#define rept(i,t) for(int i=int(h[t]);~i;i=ne[i])
#define reph(i,t,h) for(int i=int(h[t]);~i;i=ne[i])
#define x first
#define y second
#define pb push_back
#define pf push_front
#define ppb pop_back
#define ppf pop_front
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long long ll;
typedef unsigned long long lll;
typedef pair PII;
typedef pair PDD;
const int INF=0x3f3f3f3f,mod=1e9+7;
const ll INFF=1e18;
const double eps=1e-14;
mt19937 mrand(random_device{}());
template ostream& operator <<(ostream& out, const pair &p) {
    return out << "(" << p.x << " " << p.y << ")";
}
template ostream& operator <<(ostream& out, const vector &v) {
    rep(i, 0, sz(v)) {
        if(i) out << " ";
        out << v[i];
    }
    return out;
}
int rnd(int x){return mrand()%x;}
ll qmi(ll a,ll b){ll res=1;a%=mod;while(b){if(b&1)res=res*a%mod;a=a*a%mod;b>>=1;}return res;}
ll qmul(ll a,ll b){ll res=0;a%=mod;while(b){if(b&1) res=(res+a)%mod;a=(a+a)%mod;b>>=1;} return res;}
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
/*ll read()
{
    ll x=0,f=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9')x=x*10+(c-'0'),c=getchar();
    return f*x;
}*/
//#include 
//#include 
//#include 
//#include 
//#include 
//using namespace std;
//int main()
//{
//    int ok = 0;
//    int n = 50;
//    for (int i = 1; i <= n; ++i)
//    {
//        system("make.exe > make.txt");
//        system("std.exe < make.txt > std.txt");
//        double begin = clock();
//        system("baoli.exe < make.txt > baoli.txt");
//        double end = clock();
//
//        double t = (end - begin);
//        if (system("fc std.txt baoli.txt"))
//        {
//            printf("测试点#%d Wrong Answer\n", i);
//        }
//        else if (t > 1000) //1秒
//        {
//            printf("测试点#%d Time Limited Exceeded 用时 %.0lfms\n", i, t);
//        }
//        else
//        {
//            printf("测试点#%d Accepted 用时%.0lfms\n", i, t);
//            ok++; //AC数量+1
//        }
//    }
//    printf("\n");
//    double res = 100.0 * ok / n;
//    printf("共 %d 组测试数据，AC数据 %d 组。 得分%.1lf。", n, ok, res);
//
//    Sleep(1000); //休眠1秒，为了节约对拍次数。
//}
inline int read()
{
    int x=0;
    char ch;
    bool fx=false;
    do ch=getchar();while(~ch&&ch!='-'&&(ch<48||ch>57));
    if(ch=='-')fx=true,ch=getchar();
    for(;ch>47&&ch<58;ch=getchar())
        x=(x<<1)+(x<<3)+(ch^48);
    return fx?-x:x;
}
const int N=520;
PII q[N*N];
bool st[N][N];
int n,m;
int g[N][N];
int d[4][2]={{1,0},{0,1},{-1,0},{0,-1}};
void bfs(int sx,int sy)
{
	int hh=0,tt=0;
	q[0]={sx,sy};
	st[sx][sy]=1;
	while(hh<=tt)
	{
		PII t=q[hh++];
		rep(i,0,4)
		{
			int a=t.x+d[i][0],b=t.y+d[i][1];
			if(a<0||a>=n||b<0||b>=m) continue;
			if(st[a][b]||g[a][b]==0) continue;
			q[++tt]={a,b};st[a][b]=1;
		}	
	}	
}
int main()
{
#ifdef my_test
 	freopen(".in","r",stdin);
    freopen(".out","w",stdout);
#endif
#ifdef my_dp
	while(1)
	{
		system("data.exe > in.txt");
		system("brute.exe < in.txt > brute.txt");
		system("std.exe < in.txt > std.txt");
		if(system("fc std.txt brute.txt"))
			break;
	}
#endif
#ifdef my_dp2
    while (1) //一直循环，直到找到不一样的数据
    {
        system("data.exe");
        system("baoli.exe");
        system("std.exe");
        if (system("fc std.txt baoli.txt")) //当 fc 返回1时，说明这时数据不一样
            break;                          //不一样就跳出循环
    }
#endif
	clock_t start,end;
    start=clock();
	n=read(),m=read();
	int cnt=0;
	rep(i,0,n) rep(j,0,m) g[i][j]=read();
	rep(i,0,n) rep(j,0,m) if(!st[i][j]&&g[i][j]==1) cnt++,bfs(i,j);
	printf("%d\n",cnt);
    end=clock();
//    printf("%lfms\n",(double)(end-start)/CLOCKS_PER_SEC*1000);
    return 0;
}
5

http://ybt.ssoier.cn:8088/problem_show.php?pid=1359

有点意思的一道题，如何求围住的面积？先从外面去包围，如果被围住是不可能被扫到的，然后再对里面的没有被扫到的去bfs，每扩展一个块，加一块的面积。

点击查看代码 
#include
#define rep(i,l,r) for(int i=int(l);i=int(l);i--)
#define repg(i,l,r) for(i=int(l);i=int(l);i--)
#define rept(i,t) for(int i=int(h[t]);~i;i=ne[i])
#define reph(i,t,h) for(int i=int(h[t]);~i;i=ne[i])
#define x first
#define y second
#define pb push_back
#define pf push_front
#define ppb pop_back
#define ppf pop_front
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long long ll;
typedef unsigned long long lll;
typedef pair PII;
typedef pair PDD;
const int INF=0x3f3f3f3f,mod=1e9+7;
const ll INFF=1e18;
const double eps=1e-14;
mt19937 mrand(random_device{}());
template ostream& operator <<(ostream& out, const pair &p) {
    return out << "(" << p.x << " " << p.y << ")";
}
template ostream& operator <<(ostream& out, const vector &v) {
    rep(i, 0, sz(v)) {
        if(i) out << " ";
        out << v[i];
    }
    return out;
}
int rnd(int x){return mrand()%x;}
ll qmi(ll a,ll b){ll res=1;a%=mod;while(b){if(b&1)res=res*a%mod;a=a*a%mod;b>>=1;}return res;}
ll qmul(ll a,ll b){ll res=0;a%=mod;while(b){if(b&1) res=(res+a)%mod;a=(a+a)%mod;b>>=1;} return res;}
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
/*ll read()
{
    ll x=0,f=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9')x=x*10+(c-'0'),c=getchar();
    return f*x;
}*/
//#include 
//#include 
//#include 
//#include 
//#include 
//using namespace std;
//int main()
//{
//    int ok = 0;
//    int n = 50;
//    for (int i = 1; i <= n; ++i)
//    {
//        system("make.exe > make.txt");
//        system("std.exe < make.txt > std.txt");
//        double begin = clock();
//        system("baoli.exe < make.txt > baoli.txt");
//        double end = clock();
//
//        double t = (end - begin);
//        if (system("fc std.txt baoli.txt"))
//        {
//            printf("测试点#%d Wrong Answer\n", i);
//        }
//        else if (t > 1000) //1秒
//        {
//            printf("测试点#%d Time Limited Exceeded 用时 %.0lfms\n", i, t);
//        }
//        else
//        {
//            printf("测试点#%d Accepted 用时%.0lfms\n", i, t);
//            ok++; //AC数量+1
//        }
//    }
//    printf("\n");
//    double res = 100.0 * ok / n;
//    printf("共 %d 组测试数据，AC数据 %d 组。 得分%.1lf。", n, ok, res);
//
//    Sleep(1000); //休眠1秒，为了节约对拍次数。
//}
inline int read()
{
    int x=0;
    char ch;
    bool fx=false;
    do ch=getchar();while(~ch&&ch!='-'&&(ch<48||ch>57));
    if(ch=='-')fx=true,ch=getchar();
    for(;ch>47&&ch<58;ch=getchar())
        x=(x<<1)+(x<<3)+(ch^48);
    return fx?-x:x;
}
const int N=520;
int g[N][N];
bool st[N][N];
PII q[N*N];
int d[4][2]={{1,0},{0,1},{-1,0},{0,-1}};
int cnt;
void bfs(int sx,int sy)
{
	int hh=0,tt=0;
	q[0]={sx,sy};
	st[sx][sy]=1;
	while(hh<=tt)
	{
		PII t=q[hh++];
		rep(i,0,4)
		{
			int a=t.x+d[i][0],b=t.y+d[i][1];
			if(a<0||a>=10||b<0||b>=10) continue;
			if(g[a][b]||st[a][b]) continue;
			q[++tt]={a,b},st[a][b]=1; 
		}
	}
}
void bfs_cnt(int sx,int sy)
{
	cnt++;
	int hh=0,tt=0;
	q[0]={sx,sy};
	st[sx][sy]=1;
	while(hh<=tt)
	{
		PII t=q[hh++];
		rep(i,0,4)
		{
			int a=t.x+d[i][0],b=t.y+d[i][1];
			if(a<0||a>=10||b<0||b>=10) continue;
			if(g[a][b]||st[a][b]) continue;
			q[++tt]={a,b},st[a][b]=1;
			++cnt;
		}
	}
}
int main()
{
#ifdef my_test
 	freopen(".in","r",stdin);
    freopen(".out","w",stdout);
#endif
#ifdef my_dp
	while(1)
	{
		system("data.exe > in.txt");
		system("brute.exe < in.txt > brute.txt");
		system("std.exe < in.txt > std.txt");
		if(system("fc std.txt brute.txt"))
			break;
	}
#endif
#ifdef my_dp2
    while (1) //一直循环，直到找到不一样的数据
    {
        system("data.exe");
        system("baoli.exe");
        system("std.exe");
        if (system("fc std.txt baoli.txt")) //当 fc 返回1时，说明这时数据不一样
            break;                          //不一样就跳出循环
    }
#endif
	clock_t start,end;
    start=clock();
	rep(i,0,10) rep(j,0,10) g[i][j]=read();
	rep(i,0,10) if(g[0][i]==0) bfs(0,i);
	rep(i,0,10) if(g[9][i]==0) bfs(9,i);
	rep(i,0,10) if(g[i][0]==0) bfs(i,0);
	rep(i,0,10) if(g[i][9]==0) bfs(i,9);
	rep(i,0,10) rep(j,0,10) if(!g[i][j]&&!st[i][j])bfs_cnt(i,j);
	printf("%d\n",cnt);
    end=clock();
//    printf("%lfms\n",(double)(end-start)/CLOCKS_PER_SEC*1000);
    return 0;
}
6

http://ybt.ssoier.cn:8088/problem_show.php?pid=1362

忘了加新的状态wa了...一道一维的bfs

点击查看代码 
#include
#define rep(i,l,r) for(int i=int(l);i=int(l);i--)
#define repg(i,l,r) for(i=int(l);i=int(l);i--)
#define rept(i,t) for(int i=int(h[t]);~i;i=ne[i])
#define reph(i,t,h) for(int i=int(h[t]);~i;i=ne[i])
#define x first
#define y second
#define pb push_back
#define pf push_front
#define ppb pop_back
#define ppf pop_front
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long long ll;
typedef unsigned long long lll;
typedef pair PII;
typedef pair PDD;
const int INF=0x3f3f3f3f,mod=1e9+7;
const ll INFF=1e18;
const double eps=1e-14;
mt19937 mrand(random_device{}());
template ostream& operator <<(ostream& out, const pair &p) {
    return out << "(" << p.x << " " << p.y << ")";
}
template ostream& operator <<(ostream& out, const vector &v) {
    rep(i, 0, sz(v)) {
        if(i) out << " ";
        out << v[i];
    }
    return out;
}
int rnd(int x){return mrand()%x;}
ll qmi(ll a,ll b){ll res=1;a%=mod;while(b){if(b&1)res=res*a%mod;a=a*a%mod;b>>=1;}return res;}
ll qmul(ll a,ll b){ll res=0;a%=mod;while(b){if(b&1) res=(res+a)%mod;a=(a+a)%mod;b>>=1;} return res;}
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
/*ll read()
{
    ll x=0,f=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9')x=x*10+(c-'0'),c=getchar();
    return f*x;
}*/
//#include 
//#include 
//#include 
//#include 
//#include 
//using namespace std;
//int main()
//{
//    int ok = 0;
//    int n = 50;
//    for (int i = 1; i <= n; ++i)
//    {
//        system("make.exe > make.txt");
//        system("std.exe < make.txt > std.txt");
//        double begin = clock();
//        system("baoli.exe < make.txt > baoli.txt");
//        double end = clock();
//
//        double t = (end - begin);
//        if (system("fc std.txt baoli.txt"))
//        {
//            printf("测试点#%d Wrong Answer\n", i);
//        }
//        else if (t > 1000) //1秒
//        {
//            printf("测试点#%d Time Limited Exceeded 用时 %.0lfms\n", i, t);
//        }
//        else
//        {
//            printf("测试点#%d Accepted 用时%.0lfms\n", i, t);
//            ok++; //AC数量+1
//        }
//    }
//    printf("\n");
//    double res = 100.0 * ok / n;
//    printf("共 %d 组测试数据，AC数据 %d 组。 得分%.1lf。", n, ok, res);
//
//    Sleep(1000); //休眠1秒，为了节约对拍次数。
//}
inline int read()
{
    int x=0;
    char ch;
    bool fx=false;
    do ch=getchar();while(~ch&&ch!='-'&&(ch<48||ch>57));
    if(ch=='-')fx=true,ch=getchar();
    for(;ch>47&&ch<58;ch=getchar())
        x=(x<<1)+(x<<3)+(ch^48);
    return fx?-x:x;
}
const int N=520;
int n,k,cnt,maxn;
int q[N*N];
bool st[N];
int g[N][N];
int bfs(int s)
{
	int res=1;
	int hh=0,tt=0;
	st[s]=1;
	q[0]=s;
	while(hh<=tt)
	{
		int t=q[hh++];
		rep(i,1,n+1) if(g[t][i]&&!st[i]) q[++tt]=i,st[i]=1,res++; 
	}	
	return res;
}
int main()
{
#ifdef my_test
 	freopen(".in","r",stdin);
    freopen(".out","w",stdout);
#endif
#ifdef my_dp
	while(1)
	{
		system("data.exe > in.txt");
		system("brute.exe < in.txt > brute.txt");
		system("std.exe < in.txt > std.txt");
		if(system("fc std.txt brute.txt"))
			break;
	}
#endif
#ifdef my_dp2
    while (1) //一直循环，直到找到不一样的数据
    {
        system("data.exe");
        system("baoli.exe");
        system("std.exe");
        if (system("fc std.txt baoli.txt")) //当 fc 返回1时，说明这时数据不一样
            break;                          //不一样就跳出循环
    }
#endif
	clock_t start,end;
    start=clock();
	n=read(),k=read();
	while(k--) 
	{
		int a,b;a=read(),b=read();g[a][b]=1,g[b][a]=1;
	}
	rep(i,1,n+1) if(!st[i]) maxn=max(maxn,bfs(i)),cnt++;
	printf("%d %d\n",cnt,maxn);
    end=clock();
//    printf("%lfms\n",(double)(end-start)/CLOCKS_PER_SEC*1000);
    return 0;
}
7

http://ybt.ssoier.cn:8088/problem_show.php?pid=1360

如果开头和结尾一样的话，那么按照规则走是走不到的，但是确实一定可以走到的，所以在考虑能不能走到的情况，要考虑起点和终点相同的情况

点击查看代码 
#include
#define rep(i,l,r) for(int i=int(l);i=int(l);i--)
#define repg(i,l,r) for(i=int(l);i=int(l);i--)
#define rept(i,t) for(int i=int(h[t]);~i;i=ne[i])
#define reph(i,t,h) for(int i=int(h[t]);~i;i=ne[i])
#define x first
#define y second
#define pb push_back
#define pf push_front
#define ppb pop_back
#define ppf pop_front
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long long ll;
typedef unsigned long long lll;
typedef pair PII;
typedef pair PDD;
const int INF=0x3f3f3f3f,mod=1e9+7;
const ll INFF=1e18;
const double eps=1e-14;
mt19937 mrand(random_device{}());
template ostream& operator <<(ostream& out, const pair &p) {
    return out << "(" << p.x << " " << p.y << ")";
}
template ostream& operator <<(ostream& out, const vector &v) {
    rep(i, 0, sz(v)) {
        if(i) out << " ";
        out << v[i];
    }
    return out;
}
int rnd(int x){return mrand()%x;}
ll qmi(ll a,ll b){ll res=1;a%=mod;while(b){if(b&1)res=res*a%mod;a=a*a%mod;b>>=1;}return res;}
ll qmul(ll a,ll b){ll res=0;a%=mod;while(b){if(b&1) res=(res+a)%mod;a=(a+a)%mod;b>>=1;} return res;}
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
/*ll read()
{
    ll x=0,f=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9')x=x*10+(c-'0'),c=getchar();
    return f*x;
}*/
//#include 
//#include 
//#include 
//#include 
//#include 
//using namespace std;
//int main()
//{
//    int ok = 0;
//    int n = 50;
//    for (int i = 1; i <= n; ++i)
//    {
//        system("make.exe > make.txt");
//        system("std.exe < make.txt > std.txt");
//        double begin = clock();
//        system("baoli.exe < make.txt > baoli.txt");
//        double end = clock();
//
//        double t = (end - begin);
//        if (system("fc std.txt baoli.txt"))
//        {
//            printf("测试点#%d Wrong Answer\n", i);
//        }
//        else if (t > 1000) //1秒
//        {
//            printf("测试点#%d Time Limited Exceeded 用时 %.0lfms\n", i, t);
//        }
//        else
//        {
//            printf("测试点#%d Accepted 用时%.0lfms\n", i, t);
//            ok++; //AC数量+1
//        }
//    }
//    printf("\n");
//    double res = 100.0 * ok / n;
//    printf("共 %d 组测试数据，AC数据 %d 组。 得分%.1lf。", n, ok, res);
//
//    Sleep(1000); //休眠1秒，为了节约对拍次数。
//}
inline int read()
{
    int x=0;
    char ch;
    bool fx=false;
    do ch=getchar();while(~ch&&ch!='-'&&(ch<48||ch>57));
    if(ch=='-')fx=true,ch=getchar();
    for(;ch>47&&ch<58;ch=getchar())
        x=(x<<1)+(x<<3)+(ch^48);
    return fx?-x:x;
}
const int N=520;
int q[N*N];
int g[N];
int dist[N]; 
int f[2]={1,-1};
int n,s,e;
int bfs(int s)
{
	memset(dist,-1,sizeof(dist));
	int cnt=0;
	int hh=0,tt=0;
	q[0]=s;
	dist[s]=0;
	if(s==e) return 0;
	while(hh<=tt)
	{
		int t=q[hh++];
		rep(i,0,2)
		{
			int a=t+f[i]*g[t];
			if(a<=0||a>n) continue;
			if(dist[a]!=-1)continue;
			dist[a]=dist[t]+1;q[++tt]=a;
			if(a==e) return dist[a];
		}
	}
	return -1;
}
int main()
{
#ifdef my_test
 	freopen(".in","r",stdin);
    freopen(".out","w",stdout);
#endif
#ifdef my_dp
	while(1)
	{
		system("data.exe > in.txt");
		system("brute.exe < in.txt > brute.txt");
		system("std.exe < in.txt > std.txt");
		if(system("fc std.txt brute.txt"))
			break;
	}
#endif
#ifdef my_dp2
    while (1) //一直循环，直到找到不一样的数据
    {
        system("data.exe");
        system("baoli.exe");
        system("std.exe");
        if (system("fc std.txt baoli.txt")) //当 fc 返回1时，说明这时数据不一样
            break;                          //不一样就跳出循环
    }
#endif
	clock_t start,end;
    start=clock();
	n=read(),s=read(),e=read();
	rep(i,1,n+1) g[i]=read(); 
	printf("%d\n",bfs(s));
    end=clock();
//    printf("%lfms\n",(double)(end-start)/CLOCKS_PER_SEC*1000);
    return 0;
}
8

http://ybt.ssoier.cn:8088/problem_show.php?pid=1361

一开始想着能不能直接bfs把所有的数字全部扫出来，后来发现不知道为什么1000的数据会错。感觉可能是判断出了问题
后来想了想不用这样做，因为实际上是一个选数问题，且位与位之间是独立的，那么只要把每一个所能到达的所有点的数相乘，就可以得到最后所有的可能结果了。
syc的oj上是高精度，打个高精度乘法就可了

点击查看代码 
#include
#define rep(i,l,r) for(int i=int(l);i=int(l);i--)
#define repg(i,l,r) for(i=int(l);i=int(l);i--)
#define rept(i,t) for(int i=int(h[t]);~i;i=ne[i])
#define reph(i,t,h) for(int i=int(h[t]);~i;i=ne[i])
#define x first
#define y second
#define pb push_back
#define pf push_front
#define ppb pop_back
#define ppf pop_front
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long long ll;
typedef unsigned long long lll;
typedef pair PII;
typedef pair PDD;
const int INF=0x3f3f3f3f,mod=1e9+7;
const ll INFF=1e18;
const double eps=1e-14;
mt19937 mrand(random_device{}());
template ostream& operator <<(ostream& out, const pair &p) {
    return out << "(" << p.x << " " << p.y << ")";
}
template ostream& operator <<(ostream& out, const vector &v) {
    rep(i, 0, sz(v)) {
        if(i) out << " ";
        out << v[i];
    }
    return out;
}
int rnd(int x){return mrand()%x;}
ll qmi(ll a,ll b){ll res=1;a%=mod;while(b){if(b&1)res=res*a%mod;a=a*a%mod;b>>=1;}return res;}
ll qmul(ll a,ll b){ll res=0;a%=mod;while(b){if(b&1) res=(res+a)%mod;a=(a+a)%mod;b>>=1;} return res;}
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
/*ll read()
{
    ll x=0,f=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9')x=x*10+(c-'0'),c=getchar();
    return f*x;
}*/
//#include 
//#include 
//#include 
//#include 
//#include 
//using namespace std;
//int main()
//{
//    int ok = 0;
//    int n = 50;
//    for (int i = 1; i <= n; ++i)
//    {
//        system("make.exe > make.txt");
//        system("std.exe < make.txt > std.txt");
//        double begin = clock();
//        system("baoli.exe < make.txt > baoli.txt");
//        double end = clock();
//
//        double t = (end - begin);
//        if (system("fc std.txt baoli.txt"))
//        {
//            printf("测试点#%d Wrong Answer\n", i);
//        }
//        else if (t > 1000) //1秒
//        {
//            printf("测试点#%d Time Limited Exceeded 用时 %.0lfms\n", i, t);
//        }
//        else
//        {
//            printf("测试点#%d Accepted 用时%.0lfms\n", i, t);
//            ok++; //AC数量+1
//        }
//    }
//    printf("\n");
//    double res = 100.0 * ok / n;
//    printf("共 %d 组测试数据，AC数据 %d 组。 得分%.1lf。", n, ok, res);
//
//    Sleep(1000); //休眠1秒，为了节约对拍次数。
//}
inline int read()
{
    int x=0;
    char ch;
    bool fx=false;
    do ch=getchar();while(~ch&&ch!='-'&&(ch<48||ch>57));
    if(ch=='-')fx=true,ch=getchar();
    for(;ch>47&&ch<58;ch=getchar())
        x=(x<<1)+(x<<3)+(ch^48);
    return fx?-x:x;
}
const int N=5200;
bool st[N];
PII g[N];
int a[N];
int q[N*N];
int n,k,cnt;
int bfs(int s)
{
	memset(st,0,sizeof(st));
	int hh=0,tt=0;
	q[0]=s;st[s]=1;
	while(hh<=tt)
	{
		int t=q[hh++];
		rep(i,1,cnt+1)
		{
			if(t!=g[i].x) continue;
			if(st[g[i].y]) continue;
			st[g[i].y]=1,q[++tt]=g[i].y;
		}
	}
	return ++tt;
}
int main()
{
#ifdef my_test
 	freopen(".in","r",stdin);
    freopen(".out","w",stdout);
#endif
#ifdef my_dp
	while(1)
	{
		system("data.exe > in.txt");
		system("brute.exe < in.txt > brute.txt");
		system("std.exe < in.txt > std.txt");
		if(system("fc std.txt brute.txt"))
			break;
	}
#endif
#ifdef my_dp2
    while (1) //一直循环，直到找到不一样的数据
    {
        system("data.exe");
        system("baoli.exe");
        system("std.exe");
        if (system("fc std.txt baoli.txt")) //当 fc 返回1时，说明这时数据不一样
            break;                          //不一样就跳出循环
    }
#endif
	clock_t start,end;
    start=clock();
	n=read(),k=read();
	rep(i,1,k+1) 
	{
		int a,b;a=read(),b=read();
		if(b==0) continue;
		g[++cnt]={a,b};
	}
	int num=0,ans=1;
	while(n) a[num++]=n%10,n/=10;
	rep(i,0,num) ans*=bfs(a[i]);
	printf("%d\n",ans);
    end=clock();
//    printf("%lfms\n",(double)(end-start)/CLOCKS_PER_SEC*1000);
    return 0;
}
一本通数据结构队列

相关

数据结构--栈（C语言实现）

队列的顺序/链式存储实现

实现延迟消息队列

顺序存储的循环队列（c++实现）

数据结构----单链表升级版

数据结构/PTA-畅通工程之最低成本建设问题-畅通工程之局部最小花费问题/图/最小生成树

数据结构+java中常用的集合类

数据结构 之二叉树

数据结构与算法之PHP查找算法（哈希查找）

数据结构与算法之PHP查找算法（二分查找）

数据结构与算法之PHP排序算法（冒泡排序）

03java算法与数据结构------环形队列代码实现

标签