郑州大学算法设计与分析实验7

1

#include <bits/stdc++.h> 
#define rep(i,a,b) for(register int i = (a); i <= (b); ++i)
#define fep(i,a,b) for(register int i = (a); i >= (b); --i)
#define ls p<<1
#define rs p<<1|1
#define PII pair<int, int>
#define ll long long
#define ull unsigned long long
#define db double
#define endl '\n'
#define debug(a) cout<<#a<<"="<<a<<endl;
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define INF 0x3f3f3f3f 
#define x first
#define y second
using namespace std;
const int N=60;
int n,m;
int ans[N];
void dfs(int x, int y)
{
	if(!x)
	{
		cout<<n<<"=";
		rep(i,1,m)
			if(i!=m)	cout<<ans[i]<<"+";
			else	cout<<ans[i];
		cout<<endl;
	}
	rep(i,y,x)	
	{
		ans[++m]=i;
		dfs(x-i, i);
		ans[m--]=0;
	}
}

void sovle()
{
	cin>>n;
	dfs(n,1);
}

int main()
{
	IOS	
//  	freopen("1.in", "r", stdin);
//	cin >> t;
//	while(t --)	
    sovle();
}

2

#include <bits/stdc++.h> 
#define rep(i,a,b) for(register int i = (a); i <= (b); ++i)
#define fep(i,a,b) for(register int i = (a); i >= (b); --i)
#define ls p<<1
#define rs p<<1|1
#define PII pair<int, int>
#define ll long long
#define ull unsigned long long
#define db double
#define endl '\n'
#define debug(a) cout<<#a<<"="<<a<<endl;
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define INF 0x3f3f3f3f 
#define x first
#define y second
using namespace std;
const int N = 4010, mod=2147483648;
int t; 
ll f[N];
void solve()
{
	int n; cin >> n;
	rep(i,1,n)	f[i]=0;	
	f[0]=1;
    rep(i,1,n)	rep(j,i,n)	f[j]=(ll)(f[j]+f[j - i])%mod;
    cout << f[n] << endl;
}

int main()
{
	IOS	
//  	freopen("1.in", "r", stdin);
	cin >> t;
	while(t --)	
	solve();
	return 0;
}

3

#include <bits/stdc++.h> 
#define rep(i,a,b) for(register int i = (a); i <= (b); ++i)
#define fep(i,a,b) for(register int i = (a); i >= (b); --i)
#define ls p<<1
#define rs p<<1|1
#define PII pair<int, int>
#define ll long long
#define ull unsigned long long
#define db double
#define endl '\n'
#define debug(a) cout<<#a<<"="<<a<<endl;
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define INF 0x3f3f3f3f 
#define x first
#define y second
using namespace std;
const int N = 1e5, mod=2147483648;
int t, n, c, a[N],sum;
vector<int>ans;
void dfs(int u, int k)
{
	if(k>c)	return;
	if(k==c)
	{
		rep(i,0,ans.size()-1)	cout<<ans[i]<<' ';
		cout<<endl;
		exit(0);
	}
	if(u==n+1&&k!=c)	return;

	if(k+a[u]<=c)
	{
		ans.push_back(a[u]);
		dfs(u+1,k+a[u]);
		ans.pop_back();
	}
	dfs(u+1,k);
}

void solve()
{
	cin>>n>>c;
	rep(i,1,n)	cin>>a[i],sum+=a[i];
    if(sum<c)  
    {
        cout<<"No Solution!"<<endl;
        return;
    }
	dfs(1,0);
	cout<<"No Solution!"<<endl;
}

int main()
{
	IOS	
//  	freopen("1.in", "r", stdin);
//	cin >> t;
//	while(t --)	
	solve();
	return 0;
}

4

#include <bits/stdc++.h> 
#define rep(i,a,b) for(register int i = (a); i <= (b); ++i)
#define fep(i,a,b) for(register int i = (a); i >= (b); --i)
#define ls p<<1
#define rs p<<1|1
#define PII pair<int, int>
#define ll long long
#define ull unsigned long long
#define db double
#define endl '\n'
#define debug(a) cout<<#a<<"="<<a<<endl;
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define INF 0x3f3f3f3f 
#define x first
#define y second
using namespace std;

const int N = 9, M = 1 << N;

int ones[M], logg[M];
int row[N], col[N], cell[3][3];
char str[100];

void init()
{
	rep(i,0,N-1)	row[i] = col[i] = (1 << N) - 1;
    rep(i,0,2)	rep(j,0,2)	cell[i][j] = (1 << N) - 1;
}

void draw(int x, int y, int t, bool is_set)
{
    if (is_set) str[x * N + y] = '1' + t;
    else str[x * N + y] = '.';
    int v = 1 << t;
    if (!is_set) v = -v;
    row[x] -= v;
    col[y] -= v;
    cell[x / 3][y / 3] -= v;
}

int lowbit(int x)
{
    return x & -x;
}

int get(int x, int y)
{
    return row[x] & col[y] & cell[x / 3][y / 3];
}

bool dfs(int cnt)
{
    if (!cnt) return true;

    int minv = 10;
    int x, y;
	rep(i,0,N-1) rep(j,0,N-1)
        if (str[i * N + j] == '.')
        {
            int state = get(i, j);
            if (ones[state] < minv)
            {
                minv = ones[state];
                x = i, y = j;
            }
        }

    int state = get(x, y);
    for (int i = state; i; i -= lowbit(i))
    {
        int t = logg[lowbit(i)];
        draw(x, y, t, true);
        if (dfs(cnt - 1)) return true;
        draw(x, y, t, false);
    }

    return false;
}

int main()
{
//	IOS	
//  	freopen("1.in", "r", stdin);
//	cin >> t;
//	while(t --)	
    rep(i,0,N-1) logg[1 << i] = i;
    rep(i,0,(1<<N)-1)	rep(j,0,N-1)	ones[i] += i >> j & 1;

    while (cin >> str, str[0] != 'e')
    {
        init();

        int cnt = 0;
        for (int i = 0, k = 0; i < N; i ++ )
            for (int j = 0; j < N; j ++, k ++ )
                if (str[k] != '.')
                {
                    int t = str[k] - '1';
                    draw(i, j, t, true);
                }
                else cnt ++ ;

        dfs(cnt);

        puts(str);
    }

    return 0;
}

5

#include <cstring>
#include <string>
#include <algorithm>
#include <cstdio>
#include <iostream>
#define MAX_N 500
using namespace std;
 
int judge_other(string dat, int i){
    int is;
    if(dat.find("if", i) == i && (dat[i+2]==' ' || dat[i+2]=='('))
        is = 2;
    else if(dat.find("while", i) == i && (dat[i+5]==' ' || dat[i+5]=='('))
        is = 5;
    else if(dat.find("for", i) == i && (dat[i+3]==' ' || dat[i+3]=='('))
        is = 3;
    else if(dat.find("else", i) == i && dat[i+4]==' ')
        is = 4;
    else if(dat.find("{", i) == i)
        is = 1;
    else
        is = 0;   //普通语句
    return is;
}

void print_space(int space){
    for(int z=0; z<space; z++) printf(" ");
}
 
void ignore_space(string dat, int &i){
    while(dat[i]==' ') i++;
}
 
int main(){
    string dat;
    bool flag;
    getline(cin, dat);
    int i=0, j=0, m, idx, k, tmp, space=0, debt=0;  //space 记录缩进
 
    
    ignore_space(dat, i);  //去除多余空格
    //从初始字符打印至)
    idx = dat.find(')', 0);
    for(j=i; j<=idx; j++) printf("%c", dat[j]);
    printf("\n{\n");
    
    space += 2;
    i = idx+1;
    ignore_space(dat, i);
    i++;
 
    while(i < dat.length()){
        ignore_space(dat, i);
        if((tmp = judge_other(dat, i))){
            print_space(space);
            //处理{} 括号语句块  尤如{{{{}}}}
            if(tmp == 1){
                printf("{\n");
                i++;
                space += 2;
                continue;
            }
            //else特殊处理，其他的for、while、if可归为一种  均是for/while/if + () + { }
            if(tmp == 4){
                for(j=0; j<4; j++) printf("%c", dat[i+j]);
                k = i+3;
            }
            else{
                for(j=0; j<tmp; j++) printf("%c", dat[i+j]);
                printf(" ");
                i += tmp;
                ignore_space(dat, i);
                //因以 ) 作为处理标志，因此考虑 if(条件) 条件中也有()的情况
                k = i;
                int t=0;
                while(true){
                    if(dat[k] == '('){
                        t++;
                    }
                    else if(dat[k] == ')'){
                        t--;
                        if(!t) break;
                    }
                    k++;
                }
                for(j=i; j<=k; j++) printf("%c", dat[j]);
            }
            //找 { 
            //此处分两种情况：一、源代码中没有{}，语句块仅有一条语句； 二、源代码中本身有{}
            m = k+1;
            ignore_space(dat, m);
            if(dat[m] != '{'){
                printf(" {\n");
                flag = false;    //flag 与debt 共同作用为处理上述情况一，因为要考虑何时应该输出 }(即配对的右大括号)
                debt++;
                i = m;
            }else{
                printf(" {\n");
                flag = true;
                i = m+1;
            }
            space += 2;
        }
        else if(dat[i] == '}'){
            space -= 2;
            print_space(space);
            printf("}\n");
            if(space == 0) break;   //字符串处理完毕——此处用意为考虑 可能在程序的最后有空格
 
            i++;
 
            //下边几行代码即为判断上述情况一，是否应该输出 } 
            ignore_space(dat, i);
            while(debt && judge_other(dat, i)!=4){  
                space -= 2;
                print_space(space);
                printf("}\n");
                debt--;
            }
        }
        else{
            //普通语句
            idx = dat.find(';', i);
            print_space(space);
            for(j=i; j<=idx; j++) printf("%c", dat[j]);
            printf("\n");
            i = idx+1;
            if(debt && !flag){
                space -= 2;
                print_space(space);
                printf("}\n");
                debt--;
 
                //下边几行代码同为判断上述情况一，是否应该输出 } 
                ignore_space(dat, i);
                while(debt && judge_other(dat, i)!=4){
                    space -= 2;
                    debt--;
                    print_space(space);
                    printf("}\n");
                }
            }
        }
    }
    return 0;
}

6

#include <bits/stdc++.h> 
#define rep(i,a,b) for(register int i = (a); i <= (b); ++i)
#define fep(i,a,b) for(register int i = (a); i >= (b); --i)
#define ls p<<1
#define rs p<<1|1
#define PII pair<int, int>
#define ll long long
#define ull unsigned long long
#define db double
#define endl '\n'
#define debug(a) cout<<#a<<"="<<a<<endl;
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define INF 0x3f3f3f3f 
#define x first
#define y second
using namespace std;
const int N=20;
vector<int>a[N];
int n,m;
int f[N][N];


void sovle()
{
	cin>>n>>m;
	rep(i,0,n-1) rep(j,0,n-1)
		if(i==j)	f[i][j]=0;
		else	f[i][j]=INF; 
	rep(i,1,m)
	{
		int x,y;cin>>x>>y;
		f[x][y]=1;f[y][x]=1; 
	}
	rep(k,0,n-1)	rep(i,0,n-1)	rep(j,0,n-1)	f[i][j]=min(f[i][j],f[i][k]+f[k][j]);	
	int x,y;cin>>x>>y;
	if(f[x][y]==INF)	cout<<"There is no path between "<<x<<" and "<<y<<"."<<endl;
	else	cout<<"The length of the shortest path between "<<x<<" and "<<y<<" is "<<f[x][y]<<"."<<endl;
}

int main()
{
	IOS	
//  	freopen("1.in", "r", stdin);
//	cin >> t;
//	while(t --)	
    sovle();
}

7

#include <bits/stdc++.h> 
#define rep(i,a,b) for(register int i = (a); i <= (b); ++i)
#define fep(i,a,b) for(register int i = (a); i >= (b); --i)
#define ls p<<1
#define rs p<<1|1
#define PII pair<int, int>
#define ll long long
#define ull unsigned long long
#define db double
#define endl '\n'
#define debug(a) cout<<#a<<"="<<a<<endl;
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define INF 0x3f3f3f3f 
#define x first
#define y second
using namespace std;
const int N = 1010;

vector<int>a[N];
int n, m, ans, du[N], vis[N];
void dfs(int u)
{
	vis[u]=1;	
	for(auto item : a[u])
	{
		if(vis[item])	continue;
		dfs(item);
	}
}

void solve()
{
	cin>>n>>m;
	rep(i,1,m)
	{
		int x,y; cin>>x>>y;
		a[x].push_back(y); du[x]++;
		a[y].push_back(x); du[y]++;
	} 
	rep(i,1,n)	if(!vis[i]) dfs(i), ans++;
	if(ans!=1)
	{
		cout<<"N"<<endl;
		return;
	}	
	int cnt=0;
	rep(i,1,n)	if(du[i]&1)	cnt++;
	if(cnt==0||cnt==2)
	{
		cout<<"Y"<<endl;
		return;
	}
	cout<<"N"<<endl;	
	
}

int main()
{
	IOS	
//  	freopen("1.in", "r", stdin);
//	cin >> t;
//	while(t --)	
	solve();
	return 0;
}

8

#include <bits/stdc++.h> 
#define rep(i,a,b) for(register int i = (a); i <= (b); ++i)
#define fep(i,a,b) for(register int i = (a); i >= (b); --i)
#define ls p<<1
#define rs p<<1|1
#define PII pair<int, int>
#define ll long long
#define ull unsigned long long
#define db double
#define endl '\n'
#define debug(a) cout<<#a<<"="<<a<<endl;
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define INF 0x3f3f3f3f 
#define x first
#define y second
using namespace std;
const int N=1010;
vector<int>a[N];
int n,k;
int d[N];

int bfs(int x,int y)
{
	queue<int>q;
	rep(i,1,n)	d[i]=INF;
	d[x]=0;
	q.push(x);
	while(q.size()!=0)
	{
		auto t=q.front();q.pop();
		for(auto item:a[t])
		{
			if(d[t]+1<d[item])
			{
				d[item]=d[t]+1;
				q.push(item);
			}
		}
	}
	return d[y];
}

void sovle()
{
	cin>>n;
	rep(i,1,n-1)	
	{
		int x,y;cin>>x>>y;
		a[x].push_back(y);	a[y].push_back(x); 
	}
	cin>>k;
	while(k--)
	{
		int x,y;cin>>x>>y;
		cout<<bfs(x,y)<<endl;
	}
	return;
}

int main()
{
	IOS	
//  	freopen("1.in", "r", stdin);
//	cin >> t;
//	while(t --)	
    sovle();
}

9

#include <bits/stdc++.h> 
#define rep(i,a,b) for(register int i = (a); i <= (b); ++i)
#define fep(i,a,b) for(register int i = (a); i >= (b); --i)
#define ls p<<1
#define rs p<<1|1
#define PII pair<int, int>
#define ll long long
#define ull unsigned long long
#define db double
#define endl '\n'
#define debug(a) cout<<#a<<"="<<a<<endl;
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define INF 0x3f3f3f3f 
#define x first
#define y second
using namespace std;
const int N=510;
int n,m;
int dx[]={0,0,1,-1};
int dy[]={1,-1,0,0};
char c[N][N];
int sx,sy,ex,ey,ans=1145141919, d[N][N], vis[N][N];
queue<PII>q;
struct node
{
	int x,y,now;
	bool operator < (const node &t)const{
		return t.now>now;
	}
};
priority_queue<node>q2;


void bfs1()
{
	while(q.size())
	{
		auto t=q.front();q.pop();
		rep(i,0,3)
		{
			int nx=t.x+dx[i], ny=t.y+dy[i];
			if(nx>n||nx<1||ny>m||ny<1||vis[nx][ny])	continue;
			vis[nx][ny]=1;
			d[nx][ny]=d[t.x][t.y]+1;
			q.push({nx,ny});
		}
	}
}

void bfs2()
{
	q2.push({sx,sy,d[sx][sy]});
	vis[sx][sy]=1;
	while(q2.size())
	{
		auto t=q2.top();q2.pop();
		if(t.x==ex&&t.y==ey)	ans=min(ans,t.now);
		rep(i,0,3)	
		{
			int nx=t.x+dx[i], ny=t.y+dy[i];
			if(nx>n||nx<1||ny>m||ny<1||vis[nx][ny])	continue;
			vis[nx][ny]=1;
			q2.push({nx,ny,min(t.now,d[nx][ny])}); 
		}
	}
}

void sovle()
{
	cin>>n>>m;	
	rep(i,1,n)	rep(j,1,m)
	{
		cin>>c[i][j];
		if(c[i][j]=='+')	q.push({i,j}), vis[i][j]=1;
		else if(c[i][j]=='V')
		{
			sx=i;sy=j;
		}
		else if(c[i][j]=='J')
		{
			ex=i;ey=j;
		}
	}
	bfs1();
	rep(i,1,n)	rep(j,1,m)	vis[i][j]=0;
	bfs2();
	cout<<ans<<endl;
}

int main()
{
	IOS	
//  	freopen("1.in", "r", stdin);
//	cin >> t;
//	while(t --)	
    sovle();
}