2022.1.24

T1:长度为n的集合中哪个子集和为c

点击查看代码
#include <iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<string.h>
using namespace std;
int a[10000],ans[10000],sum[10000],n,c;
void print(int n)
{
	for (int i=1;i<n;i++)
		printf("%d ",ans[i]);
	exit(0);
}
void dfs(int x,int tot,int k)
{
	if (tot>c) return ;
	if (tot==c) print(k);
	if (tot+sum[x]<c) return ;
	for (int i=x;i<=n;i++)
	{
		ans[k]=a[i];
		dfs(i+1,tot+a[i],k+1);
	}
}
int main(void)
{
	scanf("%d%d",&n,&c);
	for (int i=1;i<=n;i++)
		scanf("%d",&a[i]);
	for (int i=n;i>0;i--)
		sum[i]=sum[i+1]+a[i];
	if (sum[1]>=c) dfs(1,0,1);	
	else printf("No Solution!");
	return 0;
}

T2:分配工作求min

跟昨天的题一毛一样 但考试一定要检查自己

交没交上去/是否保存!!!

点击查看代码
#include <bits/stdc++.h>
using namespace std;
int a[110][110],n;
int f[110], g[110], minn=1e6, tmp;
bool vis[110];
bool check() {
    tmp = 0;
    for (int i = 0; i < n; i++) tmp += a[i][f[i]];
    return tmp < minn;
}
void load() {
    minn = tmp;
    for (int i = 0; i < n; i++) g[i] = f[i];
}
void dfs(int id) {
    if (id == n) {
        if (check())
            load();
        return;
    }
    for (int i = 0; i < n; i++) {
        if (vis[i] == 0) {
            f[id] = i;
            vis[i] = 1;
            dfs(id + 1);
            vis[i] = 0;
        }
    }
}
void print() {
    printf("%d",minn);
    //for (int i = 0; i < n; i++) printf("%d ", g[i] + 1);
    printf("\n");
}
int main() {
	scanf("%d",&n);
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<n;j++)
		{
			scanf("%d",&a[i][j]);
		}
	}
    dfs(0);
    print();
    return 0;
}

T3:n个数和尽量接近c

其实直接输出c是很实惠的

点击查看代码

T4:由ABC构成的长度为n的序列中无重复的相邻子序列

//能打表就打表,另外注意三个一组判重,而非两个一组

点击查看搜索
char A='A',B='B',C='C';
char x[27][3]={{A,B,A},{B,C,A},{A,C,A},{B,A,A},{C,B,A},{C,A,A},{A,A,A},{B,B,A},{C,C,A},{A,B,B},{B,C,B},{A,C,B},{B,A,B},{C,B,B},{C,A,B},{A,A,B},{B,B,B},{C,C,B},{A,B,C},{B,C,C},{A,C,C},{B,A,C},{C,B,C},{C,A,C},{A,A,C},{B,B,C},{C,C,C}};
char a[15];
bool b[6];
long long int ans;
int n;
bool pd(int t,int i){
	if(a[t-1]==a[t-3]&&'A'+i==a[t-2]) return 0;
	return 1;
}
void search(int t){
	for(int i=0;i<3;i++){
		if(pd(t,i)){
			a[t]='A'+i;
			if(t==n) ans++;
			else search(t+1);
		}
	} 
}
表:

3,9,27,72,198,540,1476,4032,11016,30096,82224,224640

上一篇:最短路径


下一篇:天猫订单数据综合分析