61.种树(TLE)
#include<bits/stdc++.h>
using namespace std;
const int N = 210;
int n,m,a[N],ans=-0x3f3f3f3f,cnt;
bool st[N];
void dfs(int start,int u,int tot)
{
if(u>=start+n || cnt>=m)
{
ans=max(ans,tot);
return ;
}
for(int i=2;i<n;i++)
{
if(!st[u+i] && u+i<start+n)
{
st[u+i]=1;
cnt++;
dfs(start,u+i,tot+a[u+i]);
cnt--;
st[u+i]=0;
}
}
}
int main()
{
cin>>n>>m;
for(int i=0;i<n;i++) cin>>a[i];
for(int i=n;i<2*n;i++) a[i]=a[i-n];
if (m>n/2) {
cout<<"Error!"<<endl;
return 0;
}
for(int i=0;i<n;i++)
{
st[i+n-1]=1;
st[i]=1;
cnt++;
dfs(i,i,a[i]);
cnt--;
st[i]=0;
st[i+n-1]=0;
}
cout<<ans;
return 0;
}
62.盾神与砝码称重
#include<bits/stdc++.h>
using namespace std;
const int N = 110;
int x,n,m,a[N],s[N],f,st[N];
void dfs(int u,int tot)
{
if(tot>=1 && !f && abs(u)<=s[tot])
{
if(abs(u)==a[tot]) f=1;
else{
dfs(u-a[tot],tot-1);
dfs(u,tot-1);
dfs(u+a[tot],tot-1);
}
}
}
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>a[i];
}
sort(a+1,a+n+1);
for(int i=1;i<=n;i++) s[i]=a[i]+s[i-1];
for(int i=0;i<m;i++)
{
cin>>x;
f=0;
dfs(x,n);
if(f) puts("YES");
else puts("NO");
}
return 0;
}
63.最大乘积
#include<bits/stdc++.h>
using namespace std;
const int N = 110;
int T,n,m,a[N];
long int ans=-2147483648;
bool st[N];
void dfs(int cnt,int tot)
{
if(cnt>m)return;
if(cnt==m)
{
ans=ans>tot?ans:tot;
return;
}
for(int i=0;i<n;++i)
{
if(!st[i])
{
st[i]=1;
dfs(cnt+1,tot*a[i]);
st[i]=0;
}
}
}
int main()
{
cin>>T;
while(T--)
{
memset(st,0,sizeof st);
ans=-2147483648;
cin>>n>>m;
for(int i=0;i<n;i++) cin>>a[i];
dfs(0,1);
cout<<ans<<endl;
}
return 0;
}
64.邮票面值设计
#include<bits/stdc++.h>
using namespace std;
const int N = 1010;
typedef pair<int,int> PII;
int dx[4]={1,0,-1,0},dy[4]={0,1,0,-1};
char g[N][N];
int n,ans,total;
bool st[N][N];
bool bfs(int a,int b)
{
int f=0;
st[a][b]=true;
queue<PII> q;
q.push({a,b});
while(q.size())
{
auto t=q.front();
q.pop();
auto x=t.first,y=t.second;
int drown=0;
for(int i=0;i<4;i++)
{
int xx=x+dx[i],yy=y+dy[i];
if(xx>=0 && xx<n && yy>=0 && yy<n)
{
if(g[xx][yy]=='.')
{
drown=1;
break;
}
}
}
if(drown==0) f++;
for(int i=0;i<4;i++)
{
int xx=x+dx[i],yy=y+dy[i];
if(xx>=0 && xx<n && yy>=0 && yy<n)
{
if(g[xx][yy]=='#' && !st[xx][yy])
{
st[xx][yy]=true;
q.push({xx,yy});
}
}
}
}
if(f) return true;
return false;
}
int main()
{
scanf("%d",&n);
for(int i=0;i<n;i++) scanf("%s",g[i]);
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
if(g[i][j]=='#' && !st[i][j])
{
total++;
if(bfs(i,j)) ans++;
}
}
}
cout<<total-ans;
return 0;
}
66.木棍还原
#include<bits/stdc++.h>
using namespace std;
const int N = 110;
int n,sum,total,a[N],f,co;
bool st[N];
bool dfs(int u,int len,int tot,int cnt)
{
if(cnt*len==sum){
return 1;
}
if(tot==len){
if(dfs(0,len,0,cnt+1))
return 1;
}
for(int i=u;i<n;i++)
{
if(!st[i] && tot+a[i]<=len)
{
st[i]=1;
if(dfs(i+1,len,tot+a[i],cnt))
return 1;
st[i]=0;
if(a[i]==len-tot || tot==0)
break;
while(a[i]==a[i+1]) i++;
}
}
return 0;
}
int main()
{
while(cin>>n)
{
sum=0;
if(!n) break;
for(int i=0;i<n;i++)
{
cin>>a[i];
sum+=a[i];
}
sort(a,a+n,greater<int>());
for(int i=a[0];i<=sum;i++)
{
if(sum%i) continue;
else{
memset(st,0,sizeof st);
if(dfs(0,i,0,0))
{
cout<<i<<endl;
break;
}
}
}
}
return 0;
}
67.剪格子
#include<bits/stdc++.h>
using namespace std;
const int N = 15;
int g[N][N];
bool st[N][N];
int n, m;
int res = 0x3fff;
int h;
int idx[4] = {-1, 0, 1, 0}, idy[4] = {0, 1, 0, -1};
int vt[N][N];
bool cons[N][N];
int getmax()
{
int maxv = 0;
int idx = 0;
for(int i = 0; i < m * n; ++ i)
if(!cons[i / m][i % m] && g[i / m][i % m] > maxv)
{
maxv = g[i / m][i % m];
idx = i;
}
return idx;
}
void bfs(int i, int j)
{
vt[i][j] = true;
for(int k = 0; k < 4; ++ k)
{
int x = i + idx[k], y = j + idy[k];
if(x < 0 || x >= n || y < 0 || y >= m) continue;
if(vt[x][y]) continue;
if(st[x][y] != st[i][j]) continue;
bfs(x, y);
}
}
bool check()
{
int cnt = 0;
for(int i = 0; i < n; ++ i)
for(int j = 0; j < m; ++ j)
if(!vt[i][j])
{
bfs(i, j);
cnt ++;
}
if(cnt == 2)
return true;
return false;
}
void dfs(int sum, int cnt, int num, int left)
{
if(sum > h) return;
if(cnt >= res) return;
if(left == 0)
{
if(sum == h && check())
res = cnt;
memset(vt, 0, sizeof vt);
return;
}
if(sum == h)
{
if(check())
res = cnt;
memset(vt, 0, sizeof vt);
return;
}
cons[num / m][num % m] = true;
st[num / m][num % m] = true;
int maxidx = getmax();
dfs(sum + g[num / m][num % m], cnt + 1, maxidx, left - 1);
st[num / m][num % m] = false;
dfs(sum, cnt, maxidx, left - 1);
cons[num / m][num % m] = false;
}
int main()
{
cin >> m >> n;
int sum = 0;
for(int i = 0; i < n; ++ i)
for(int j = 0; j < m; ++ j)
{
cin >> g[i][j];
sum += g[i][j];
}
h = sum / 2;
if(sum != h * 2)
cout << 0;
else
{
st[0][0] = true;
cons[0][0] = true;
dfs(g[0][0], 1, getmax(), m * n - 1);
if(res != 0x3fff)
cout << res;
else
cout << 0;
}
return 0;
}
68.分考场
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
int n,m,g[110][110];
int dp[110][110],ans=110;
bool st[110];
void dfs(int u,int tot)
{
if(tot>=ans) return ;
if(u>n)
{
ans=min(ans,tot);
return ;
}
int i;
for(i=1;i<=tot;i++)
{
int k=0;
while(g[i][k] && !dp[u][g[i][k]]) k++;
if(!g[i][k])
{
g[i][k]=u;
dfs(u+1,tot);
g[i][k]=0;
}
}
g[i][0]=u;
dfs(u+1,tot+1);
g[i][0]=0;
}
int main()
{
cin>>n>>m;
int a,b;
while(m--)
{
cin>>a>>b;
dp[a][b]=dp[b][a]=1;
}
dfs(1,1);
cout<<ans;
return 0;
}
69.组合表达式
#include<bits/stdc++.h>
using namespace std;
const int N =100;
char str[N];
int n;
void dfs(int cur,int num,int tot)
{
if(cur==n){
if(tot+num==0) cout<<str<<endl;
return;
}
str[2*cur-1]=' ';
int t;
if(num>0) t=num*10+cur+1;
else t=num*10-cur-1;
dfs(cur+1,t,tot);
str[2*cur-1]='+';
dfs(cur+1,cur+1,tot+num);
str[2*cur-1]='-';
dfs(cur+1,-cur-1,tot+num);
}
int main()
{
cin>>n;
for(int i=0;i<n;i++)
str[2*i]=i+'1';
dfs(1,1,0);
return 0;
}
70.拉丁正方形
71.和最大子序列(0.8)
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
int n,m,x,sum,ans=-INT_MAX;
int a[N],q[N];
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
a[i]+=a[i-1];
}
int hh=0,tt=0;
for(int i=1;i<=n;i++)
{
ans=max(ans,a[i]-a[q[hh]]);
while(hh<=tt && a[q[tt]]>=a[i]) tt--;
q[++tt]=i;
}
cout<<ans;
return 0;
}
72.密码锁
73.最少操作数
#include<bits/stdc++.h>
using namespace std;
const int N=55;
int a[N],n,ans;
bool flag;
int main() {
cin>>n;
for (int i = 0; i < n; i++)
cin>>a[i];
while (1) {
flag = 0;
for (int i = 0; i < n; i++)
{
if(a[i]%2)
{
ans++;
a[i]--;
}
if(a[i] != 0)
flag=1;
}
if (!flag)
break;
for(int i = 0; i < n; i++)
a[i] /= 2;
ans++;
}
cout<<ans;
return 0;
}
74.最大值路径
#include<bits/stdc++.h>
using namespace std;
int n,k;
int ans;
void dfs(int sum,int u,int past)
{
if(sum>n) return ;
if(u == k)
{
if(sum == n) ans ++;
return ;
}
for(int i = past;i <= n - sum;i ++)
dfs(sum + i,u + 1,i);
}
int main()
{
cin>>n>>k;
dfs(0,0,1);
cout<<ans;
return 0;
}
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int n,m,f[50][50];
int main()
{
cin>>n>>m;
f[0][0]=1;
for(int i=1;i<=m;i++)
for(int j=0;j<n;j++)
f[i][j]=(f[i-1][(j+1)%n]+f[i-1][(j-1+n)%n]);
cout<<f[m][0];
return 0;
}
#include <iostream>
using namespace std;
const int N = 110;
int n;
int f[N];
int main()
{
cin >> n;
f[0] = 1;
for (int i = 1; i <= n; i ++ )
for (int j = i; j <= n; j ++ )
f[j] = (f[j] + f[j - i]) ;
cout << f[n] << endl;
return 0;
}
#include <bits/stdc++.h>
using namespace std;
const int N = 1e4+10;
int a[N],n,d,ans;
bool f[N];
int gcd(int a,int b)
{
return b?gcd(b,a%b):a;
}
int main()
{
cin>>n;
for (int i = 1; i <= n; i ++ )
{
cin>>a[i];
d=gcd(d,a[i]);
}
if(d!=1) puts("INF");
else{
f[0]=1;
for(int i=1;i<=n;i++)
for(int j=a[i];j<N;j++)
f[j]|=f[j-a[i]];
for (int i = 0; i < N; i ++ )
if(!f[i])
ans++;
cout<<ans;
}
return 0;
}
#include<bits/stdc++.h>
using namespace std;
const int N = 1e3+10,mod = 100000007;
int n,s,a,b;
int f[N][N];
int get_mod(int x)
{
return (x%n + n)%n;
}
int main()
{
cin>>n>>s>>a>>b;
f[0][0]=1;
for(int i=1;i<n;i++)
{
for(int j=0;j<n;j++)
{
f[i][j]=(f[i-1][get_mod(j-i*a)]+f[i-1][get_mod(j+i*b)])%mod;
}
}
cout<<f[n-1][get_mod(s)];
return 0;
}
#include<bits/stdc++.h>
using namespace std;
const int N = 2e6+10;
int n,m=N-1,k,dp[N],ans;
int main()
{
memset(dp,0x3f,sizeof dp);
dp[0]=0;
cin>>k>>n;
int x;
for(int i=0;i<n;i++)
{
cin>>x;
for(int j=x;j<=m;j++)
{
dp[j]=min(dp[j],dp[j-x]+1);
}
}
while(dp[ans]<=k) ans++;
cout<<ans-1;
return 0;
}
