41.联系 (PE)
#include<bits/stdc++.h>
using namespace std;
int n,m,r,ans,a,b,T;
string s,ss;
map<string,int> mp;
bool cmp(string a,string b)
{
if(a.size()!=b.size()) return a.size()<b.size();
return a<b;
}
int main()
{
cin>>a>>b>>n;
while(cin>>ss)
s+=ss;
for(int i=0;i<s.size();i++)
{
string t="";
for(int j=i;j<i+b && j<s.size();j++)
{
t+=s[j];
if(t.size()>=a) mp[t]++;
}
}
set<int> se;
vector<int> v;
unordered_map<int, vector<string> > hs;
for(auto x:mp)
{
se.insert(x.second);
hs[x.second].push_back(x.first);
}
for(auto x:se) v.push_back(x);
reverse(v.begin(),v.end());
for(int i=0;i<n && i<v.size();i++)
{
vector<string> temp = hs[v[i]];
sort(temp.begin(),temp.end(),cmp);
cout<<v[i]<<endl;
for(int j=0;j<temp.size();j++)
{
if(j && j%6==0) puts("");
cout<<temp[j]<<" ";
}
cout<<endl;
}
return 0;
}
42.完美的代价
#include<bits/stdc++.h>
using namespace std;
string s;
int n,co,ans;
map<char,int> mp;
int main()
{
cin>>n>>s;
for(auto x:s)
mp[x]++;
for(char i='a';i<='z';i++)
if(mp[i]%2)
co++;
if(co>1){
puts("Impossible");
}
else{
while(s.size())
{
string t=s.substr(0,1);
s.erase(0,1);
if(s.find(t)==-1)
ans+=s.size()/2;
else{
string str(s.rbegin(),s.rend());
int j=str.find(t);
ans+=j;
s.erase(s.size()-1-j,1);
}
}
cout<<ans;
}
return 0;
}
43.纪念品分组
#include<bits/stdc++.h>
using namespace std;
const int N =3e4+10;
int maxv,n,a[N],ans;
int main()
{
cin>>maxv>>n;
for(int i=0;i<n;i++) cin>>a[i];
sort(a,a+n);
deque<int> q;
for(int i=0;i<n;i++)
q.push_back(a[i]);
while(q.size())
{
if(q.size()>1)
{
if(q.back()+q.front()<=maxv)
{
q.pop_back();
q.pop_front();
ans++;
}
else{
q.pop_back();
ans++;
}
}
else{
q.pop_back();
ans++;
}
}
cout<<ans;
return 0;
}
44.旅行家的预算
#include<bits/stdc++.h>
using namespace std;
const int N =110;
int n;
double D1,D2,maxv,cur,ans;
double d[N],cost[N],needs[N];
int main()
{
cin>>D1>>maxv>>D2>>cost[0]>>n;
for(int i=1;i<=n;i++) cin>>d[i]>>cost[i];
d[n+1]=D1;
for(int i=0;i<=n;i++)
needs[i]=(d[i+1]-d[i])/D2;
int i=0,j;
while(i<n)
{
j=i+1,cur=maxv;
while(cost[i]<cost[j] && cur)
{
double t=min(needs[j],cur);
if(needs[i]+t>maxv)
t=maxv-needs[i];
needs[i]+=t;
needs[j]-=t;
cur-=t;
j++;
}
i=j;
}
for(int i=0;i<=n;i++)
{
if(needs[i]>maxv)
{
puts("No Solution");
return 0;
}
ans+=cost[i]*needs[i];
}
printf("%.2f",ans);
return 0;
}
45.盾神与积木游戏
#include<bits/stdc++.h>
using namespace std;
const int N =1e4+10;
int n,m,T,tot,a[N];
bool st[N];
struct node{
int curr,needs;
bool operator<(const node &p) const{
return needs<p.needs;
}
};
int main()
{
cin>>T;
while(T--)
{
memset(st,0,sizeof st);
vector<node> v;
tot=0;
cin>>n;
int x,y;
for(int i=0;i<n;i++)
{
cin>>x>>y;
if(x>=y)
{
tot+=x;
}
else{
v.push_back({x,y-x});
}
}
sort(v.begin(),v.end());
int j=0;
while(j<v.size())
{
if(tot>=v[j].needs)
{
tot+=v[j].curr;
j++;
}
else break;
}
if(j<v.size()) puts("NO");
else puts("YES");
}
return 0;
}
46.王、后传说
#include<bits/stdc++.h>
using namespace std;
const int N=30;
int n,a,b,cnt,ans;
bool col[N],dg[N],udg[N],st[N][N];
void dfs(int u)
{
if(u==n)
{
if(cnt==n) ans++;
return ;
}
for(int i=0;i<n;i++)
{
if(!col[i] && !st[u][i] && !dg[u+i] && !udg[u-i+n])
{
col[i]=dg[u+i]=udg[u-i+n]=1;
cnt++;
dfs(u+1);
cnt--;
col[i]=dg[u+i]=udg[u-i+n]=0;
}
}
}
int main()
{
cin>>n>>a>>b;
a--,b--;
for(int i=-1;i<=1;i++)
{
for(int j=-1;j<=1;j++)
{
int x=a+i,y=b+j;
if(x>=0 && x<n && y>=0 && y<n) st[x][y]=1;
}
}
dfs(0);
cout<<ans;
return 0;
}
47.瓷砖铺放
#include<bits/stdc++.h>
using namespace std;
int n,ans;
void dfs(int u)
{
if(u>n) return;
if(u==n)
{
ans++;
return ;
}
dfs(u+1);
dfs(u+2);
}
int main()
{
cin>>n;
dfs(0);
cout<<ans;
return 0;
}
48.FBI树
#include<bits/stdc++.h>
using namespace std;
int n;
string s;
void post(int l,int r)
{
if(l<=r)
{
int mid=(l+r)/2;
int I=0,B=0;
if(l!=r)
{
post(l,mid);
post(mid+1,r);
}
for(int i=l;i<=r;i++)
if(s[i]=='0') B++;
else I++;
if(B>0 && I>0) cout<<"F";
else if(I) cout<<"I";
else cout<<"B";
}
}
int main()
{
cin>>n;
cin>>s;
post(0,pow(2,n)-1);
return 0;
}
49.单词接龙
#include<bits/stdc++.h>
using namespace std;
int n,m,ans,st[30];
string s;
vector<string> v;
void dfs(string u)
{
ans=max(ans,(int)u.size());
for(int l=1;l<u.size();l++)
{
string t=u.substr(l);
for(int i=0;i<n;i++)
{
if(v[i].find(t)==0 && st[i]<2)
{
st[i]++;
string temp=u+v[i].substr(u.size()-l);
dfs(temp);
st[i]--;
}
}
}
}
int main()
{
cin>>n;
for(int i=0;i<n;i++)
{
cin>>s;
v.push_back(s);
}
char h;
cin>>h;
for(int i=0;i<n;i++)
{
if(v[i][0]==h)
{
memset(st,0,sizeof st);
st[i]=1;
dfs(v[i]);
}
}
cout<<ans;
return 0;
}
50.排列问题
#include<bits/stdc++.h>
using namespace std;
int n,m,ans,a[30],x,cnt;
string s;
set<int> se[10];
map<int,int> mp;
int main()
{
cin>>n>>m;
for(int i=0;i<n;i++) a[i]=i;
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
cin>>x;
if(i!=j && x==0)
se[i].insert(j);
}
}
do{
int f=0;
for(int i=0;i<n;i++)
mp[a[i]]=i;
for(int i=0;i<n;i++)
{
if(f) break;
int id=mp[i];
if(id!=n-1 && se[i].size())
for(auto x:se[i])
{
if(mp[x]==id+1)
{
f=1;
break;
}
}
}
if(!f) cnt++;
else continue;
if(cnt==m)
{
for(int i=0;i<n-1;i++) cout<<a[i]<<" ";
cout<<a[n-1]<<endl;
break;
}
}while(next_permutation(a,a+n));
return 0;
}
51.和为T
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
int n,ans;
LL m,a[30],x,cnt;
bool st[30];
void dfs(int u)
{
if(u==n)
{
LL res=0,f=0;
for(int i=0;i<n;i++)
{
if(!st[i])
{
f=1;
res+=a[i];
}
}
if(res==m && f)
{
cnt++;
for(int i=0;i<n;i++)
{
if(!st[i])
cout<<a[i]<<" ";
}
cout<<endl;
}
return ;
}
st[u]=1;
dfs(u+1);
st[u]=0;
dfs(u+1);
}
int main()
{
cin>>n;
for(int i=0;i<n;i++) cin>>a[i];
cin>>m;
dfs(0);
cout<<cnt;
return 0;
}
52.母亲的牛奶
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
int n,m,A,B,C,ans;
bool st[21][21][21];
void dfs(int a,int b,int c)
{
if(st[a][b][c]) return ;
st[a][b][c]=1;
dfs(a-min(a,B-b),min(a+b,B),c);
dfs(a-min(a,C-c),b,min(a+c,C));
dfs(min(a+b,A),b-min(b,A-a),c);
dfs(a,b-min(b,C-c),min(c+b,C));
dfs(min(a+c,A),b,c-min(c,A-a));
dfs(a,min(b+c,B),c-min(c,B-b));
}
int main()
{
cin>>A>>B>>C;
dfs(0,0,C);
vector<int> v;
for(int i=0;i<=C;i++)
{
for(int j=0;j<=B;j++)
{
if(st[0][j][i]){
v.push_back(i);
break;
}
}
}
for(int i=0;i<v.size()-1;i++) cout<<v[i]<<" ";
cout<<v[v.size()-1];
return 0;
}
53.魔板
#include<bits/stdc++.h>
using namespace std;
string s,S,ss;
int co=0;
set<string> se;
struct node{
string s,op;
};
int main()
{
getline(cin,s);
stringstream ssin(s);
while(ssin>>s)
{
if(co<4) S+=s;
else ss=s+ss;
co++;
}
S+=ss;
queue<node> q;
q.push({"12348765",""});
while(q.size())
{
auto t=q.front(); q.pop();
if(se.count(t.s)) continue;
se.insert(t.s);
if(t.s==S)
{
cout<<t.op.size()<<endl;
cout<<t.op;
break;
}
for(int i=0;i<3;i++)
{
if(i==0){
string l=t.s.substr(0,4);
string r=t.s.substr(4);
ss=r+l;
if(!se.count(ss))
q.push({ss,t.op+"A"});
}
else if(i==1){
string l=t.s[3]+t.s.substr(0,3);
string r=t.s.substr(4,3);
r=t.s[7]+r;
ss=l+r;
if(!se.count(ss))
q.push({ss,t.op+"B"});
}
else{
swap(t.s[1],t.s[2]);
swap(t.s[5],t.s[6]);
swap(t.s[1],t.s[6]);
if(!se.count(t.s))
q.push({t.s,t.op+"C"});
}
}
}
return 0;
}
54.计算器
#include<bits/stdc++.h>
using namespace std;
string S,T;
int n,co,ans;
int main()
{
int num[10][10] = {
{0, 4, 3, 3, 4, 3, 2, 3, 1, 2},
{4, 0, 5, 3, 2, 5, 6, 1, 5, 4},
{3, 5, 0, 2, 5, 4, 3, 4, 2, 3},
{3, 3, 2, 0, 3, 2, 3, 2, 2, 1},
{4, 2, 5, 3, 0, 3, 4, 3, 3, 2},
{3, 5, 4, 2, 3, 0, 1, 4, 2, 1},
{2, 6, 3, 3, 4, 1, 0, 5, 1, 2},
{3, 1, 4, 2, 3, 4, 5, 0, 4, 3},
{1, 5, 2, 2, 3, 2, 1, 4, 0, 1},
{2, 4, 3, 1, 2, 1, 2, 3, 1, 0}
};
cin>>n;
cin>>S>>T;
for(int i=0;i<n;i++)
ans+=num[S[i]-'0'][T[i]-'0'];
cout<<ans;
return 0;
}
55.学霸的迷宫(0.7)
#include<bits/stdc++.h>
using namespace std;
string S,T;
int n,m,co,ans;
int dx[4]={1,0,0,-1},dy[4]={0,-1,1,0};
char g[510][510];
struct node{
int x,y;
string op;
};
bool st[510][510];
char p[4]={'D','L','R','U'};
int main()
{
while(cin>>n>>m)
{
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
{
cin>>g[i][j];
st[i][j]=0;
}
queue<node> q;
q.push({0,0,""});
st[0][0]=1;
while(q.size())
{
auto t=q.front();
q.pop();
// cout<<t.x<<" "<<t.y<<" "<<t.op<<endl;
if(t.x==n-1 && t.y==m-1){
cout<<t.op.size()<<endl<<t.op;
break;
}
for(int i=0;i<4;i++)
{
int xx=t.x+dx[i],yy=t.y+dy[i];
if(xx<0||xx>=n||yy<0||yy>=m||st[xx][yy]||g[xx][yy]=='1')
continue;
st[xx][yy]=1;
q.push({xx,yy,t.op+p[i]});
}
}
}
return 0;
}
56.矩阵中的最长递增路径
#include<bits/stdc++.h>
using namespace std;
int n,m,g[55][55],st[55][55];
int dx[4]={1,0,-1,0},dy[4]={0,1,0,-1};
int dfs(int i, int j)
{
if (st[i][j]) return st[i][j];
int maxlen = 1;
for (int p=0;p<4;p++)
{
int x = i + dx[p], y = j + dy[p];
if (x < 0 || x >= n || y < 0 || y >= m || g[x][y] <= g[i][j]) continue;
int len = 1 + dfs(x, y);
maxlen = max(maxlen, len);
}
st[i][j] = maxlen;
return maxlen;
}
int main()
{
cin>>n>>m;
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
cin>>g[i][j];
int res = 1;
for (int i=0;i<n;i++)
{
for (int j=0;j<m;j++)
{
res = max(res,dfs(i,j));
}
}
cout<<res;
}
57.线段和点
#include<bits/stdc++.h>
using namespace std;
const int N =1e4+10;
int n,m,a[N];
struct node{
int l,r;
bool operator<(const node &p) const{
if(l!=p.l) return l<p.l;
return r>p.r;
}
}d[N];
int main()
{
cin>>n>>m;
for(int i=0;i<n;i++) cin>>a[i];
for(int i=0;i<m;i++) cin>>d[i].l>>d[i].r;
sort(d,d+m);
int i,cur=0;
for(i=0;i<n;i++)
{
int t=0;
for(int j=0;j<n;j++)
{
int k=cur;
while(k<m)
{
if(a[j]<d[k].l || d[k].r<a[j])
break;
k++;
}
if(k>t) t=k;
}
cur=t;
if(cur==m) break;
}
if(i==n) cout<<-1;
else cout<<i+1;
return 0;
}
58.矩阵翻转
59.无重叠区间
#include<bits/stdc++.h>
using namespace std;
const int N = 2e4+10;
int n;
struct node{
int l,r;
bool operator<(const node &p) const{
return r<p.r;
}
}a[N];
int main()
{
cin>>n;
for(int i=0;i<n;i++) cin>>a[i].l>>a[i].r;
sort(a,a+n);
int cnt=0,i=1,cur=a[0].r;
for(int i=1;i<n;i++)
{
if(a[i].l<cur) cnt++;
else cur=a[i].r;
}
cout<<cnt;
return 0;
}
60.超级玛丽
#include<bits/stdc++.h>
using namespace std;
const int N = 2e4+10;
int n,m,a[N],f,x;
set<int> se;
int main()
{
cin>>n>>m;
while(m--)
{
cin>>x;
a[x]=-1;
if(a[x-1]==-1 || a[x+1]==-1) f=1;
}
a[1]=1;
if(f) a[n]=0;
else{
for(int i=1;i<=n;i++)
{
if(a[i-1]!=-1 && a[i]!=-1) a[i]+=a[i-1];
if(a[i-2]!=-1 && a[i]!=-1) a[i]+=a[i-2];
}
}
cout<<a[n];
return 0;
}
