【A题目链接】点击打开链接
【题意】给了一个数n，和2*n-2个字符组成的字符串，其中奇数位置的字符是小写，偶数为大写。如果小写字符和大写字符是匹配的，那么就可以成功开门，问你要从1走到n，至少需要带多少把钥匙才能顺利开门。
【解题思路】贪心即可。把走到当前位置没用到的钥匙用一个数组hash下来然后判断一下即可。
【AC代码】
#include <bits/stdc++.h>
using namespace std;
const int maxn = 200010;
int key[200];
int n;
char s[maxn];
int main()
{
cin>>n;
cin>>s;
memset(key,0,sizeof(key));
int cnt=0;
for(int i=0; i<(int)strlen(s); i+=2)
{
if(s[i+1]+32==s[i])
{
cnt++;
}
else
{
key[s[i]-32]++;
if(key[s[i+1]]>0)
{
cnt++;
key[s[i+1]]--;
}
}
}
cout<<n-1-cnt<<endl;
return 0;
}【B题目链接】 点击打开链接
【解题思路】由于是对称的反转，所以暴力统计前一半的反转次数就可以了。
【AC代码】
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn=200010;
const int maxm=100010;
char s[maxn];
int a[maxn];
ll cnt[maxn];
int m;
int main()
{
scanf("%s",s+1);
int len=strlen(s+1);
cin>>m;
for(int i=1; i<=m; i++)
{
cin>>a[i];
cnt[a[i]]++;
}
for(int i=1; i<=len/2; i++)
{
cnt[i]+=cnt[i-1];
}
for(int i=1; i<=len/2; i++)
{
if(cnt[i]%2==1)
{
swap(s[i],s[len-i+1]);
}
}
printf("%s",s+1);
return 0;
}【C题目链接】 点击打开链接
【解题思路】给了n个木棍，并且有每一根木棍的长度，要我们找到一个最大的矩形让它的面积足最大，并且满足每根木棍的长度可以减去1。排序后贪心找最大的匹配 木棍对即可。
【AC代码】
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn=100005;
int a[maxn];
ll ans,x;
int n;
int main()
{
cin>>n;
for(int i=1; i<=n; i++)
{
cin>>a[i];
}
x=0;
sort(a+1,a+n+1);
for(int i=n-1; i>=1; i--)
{
if(a[i+1]-a[i]<2)
{
if(x) ans+=(ll)a[i]*x,x=0;
else x=a[i];
i--;
}
}
cout<<ans<<endl;
return 0;
}【D题目链接】 点击打开链接
【题意】给了一个n*m的迷宫，迷宫里面有空地用.表示，有墙用*表示，要你去掉一些墙使得最后的联通的空地都是矩形，并且要保证去掉的墙的个数最小。
【解题思路】观察样例，可以猜测具有. . . *这种形式的2*2的小迷宫都会变成. . . .，所以直接找这种形式的小迷宫，进行BFS就行了，这是贪心加BFS的应用。
【AC代码】
#include <queue>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
int n,m;
char maze[2010][2010];
int dir[8][2]={{0,1},{0,-1},{-1,0},{1,0},{1,1},{1,-1},{-1,1},{-1,-1}};
int vis[2010][2010];
queue<pair<int,int> >que;
int judge(int i,int j)
{
if(maze[i][j]=='.'||i<0||i>n-1||j<0||j>m-1) return false;
if(maze[i][j+1]=='.'&&maze[i+1][j]=='.'&&maze[i+1][j+1]=='.') return true;
if(maze[i][j-1]=='.'&&maze[i+1][j-1]=='.'&&maze[i+1][j]=='.') return true;
if(maze[i-1][j]=='.'&&maze[i-1][j+1]=='.'&&maze[i][j+1]=='.') return true;
if(maze[i][j-1]=='.'&&maze[i-1][j-1]=='.'&&maze[i-1][j]=='.') return true;
return false;
}
void BFS()
{
while(!que.empty())
{
int x=que.front().first;
int y=que.front().second;
que.pop();
maze[x][y]='.';
for(int i=0; i<8; i++)
{
int tx=x+dir[i][0];
int ty=y+dir[i][1];
if(judge(tx,ty)&&!vis[tx][ty])
{
vis[tx][ty]=true;
que.push(make_pair(tx,ty));
}
}
}
}
int main()
{
cin>>n>>m;
for(int i=0; i<n; i++) scanf("%s",maze[i]);
memset(vis,false,sizeof(vis));
for(int i=0; i<n; i++)
{
for(int j=0; j<m; j++)
{
if(judge(i,j))
{
que.push(make_pair(i,j));
vis[i][j]=true;
}
}
}
BFS();
for(int i=0; i<n; i++)
{
printf("%s\n",maze[i]);
}
return 0;
}【E题目链接】 点击打开链接
【题意】给了n个数，然后你可以改变n个数里面的k个数，使这k个数变成这个数的阶乘，问你有多少种方式能够使得这这些数的和等于s。
【解题思路】由于n最大为25个，每个数有不选，不变，变本身的阶乘3种情况，所以一共有3^25种情况，直接枚举肯定T。所以考虑另外一种做法，我们可以先算前n/2个数然后用map存储下来，再算后n/2个数，在后n/2个数中算出来的数架设为sum2如果s-sum2在前n/2个数的和中出现过，则我们找到相应个数的解，这样将复杂度降到2 * 3^12 约等于1e6的数量级，注意s的范围是10^16，而18! ＝ 6*10^15因此18以后的阶乘我们都不用去算了，搜索的时候当然也不用搜。
【AC代码】
#include <map>
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
#define ll long long
ll fac[20]={1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880,3628800, 39916800, 479001600, 6227020800 ,87178291200 ,1307674368000,20922789888000 ,355687428096000 ,6402373705728000};
int n,k;
ll a[30],s,ans;
map<ll,ll>mp[30];
void dfs1(int i,ll cnt,ll sum)
{
if(sum>s||cnt>k) return;
if(i==n/2)
{
mp[cnt][sum]++;
return ;
}
dfs1(i+1,cnt,sum);
dfs1(i+1,cnt,sum+a[i]);
if(a[i]<=18) dfs1(i+1,cnt+1,sum+fac[a[i]]);
}
void dfs2(int i,ll cnt,ll sum)
{
if(sum>s||cnt>k) return ;
if(i==n)
{
for(int j=0; j+cnt<=k; j++)
{
if(mp[j].count(s-sum))
ans+=mp[j][s-sum];
}
return ;
}
dfs2(i+1,cnt,sum);
dfs2(i+1,cnt,sum+a[i]);
if(a[i]<=18)
{
dfs2(i+1,cnt+1,sum+fac[a[i]]);
}
}
int main()
{
ans=0;
cin>>n>>k>>s;
for(int i=0; i<n; i++) cin>>a[i];
dfs1(0,0,0);
dfs2(n/2,0,0);
cout<<ans<<endl;
return 0;
}
京公网安备 11010502036488号