Acwing. 秋季每日一题
Acwing. 秋季每日一题
活动链接
A 重复局面.
国际象棋在对局时，同一局面连续或间断出现 3次或 3次以上，可由任意一方提出和棋。
国际象棋每一个局面可以用大小为 8×8的字符数组来表示，其中每一位对应棋盘上的一个格子。
六种棋子王、后、车、象、马、兵分别用字母 k、q、r、b、n、p表示，其中大写字母对应白方、小写字母对应黑方。
棋盘上无棋子处用字符 * 表示。
两个字符数组的每一位均相同则说明对应同一局面。
现已按上述方式整理好了每步棋后的局面，试统计每个局面分别是第几次出现。
A思路:
这是一个哈希表简单的应用题,我们可以将局面整个按照第一行第二行存储下来,记录每个局面出现的次数.
A代码:
#include<bits/stdc++.h>
using namespace std;
void solve(){
unordered_map<string, int> map;
int n;
cin>>n;
while(n--){
string x="";
string a;
for(int i=1;i<=8;i++){
cin>>a;
x+=a;
}
map[x]++;
cout<<map[x]<<endl;
}
}
int main(){
int t=1;
while(t--){
solve();
}
return 0;
}
B垦田计划
顿顿总共选中了 n块区域准备开垦田地，由于各块区域大小不一，开垦所需时间也不尽相同。据估算，其中第 i块（1≤i≤n）区域的开垦耗时为 ti天。
这 n块区域可以同时开垦，所以总耗时 tTotal取决于耗时最长的区域，即：
为了加快开垦进度，顿顿准备在部分区域投入额外资源来缩短开垦时间。
具体来说：
在第 i块区域每投入 ci单位资源，便可将其开垦耗时缩短 1天；
耗时缩短天数以整数记，即第 i块区域投入资源数量必须是 ci的整数倍；
在第 i块区域最多可投入 ci×(ti−k)单位资源，将其开垦耗时缩短为 k天；
这里的 k表示开垦一块区域的最少天数，满足 0<k≤min{t1,t2,…,tn}；换言之，如果无限制地投入资源，所有区域都可以用 k天完成开垦。
现在顿顿手中共有 m单位资源可供使用，试计算开垦 n块区域最少需要多少天？
B思路+代码:
非二分做法：
如果想要将耗时时间降低一天，我们就需要将所有最大天数降低一天，如果我们手里的资源不够的话，那就无法降低一天。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+10;
// struct node
// {
// int t,c;
// }a[N];
// bool cmp(node a,node b){
// if()
// }
int m1[N];
void solve(){
int n,m,k;
cin>>n>>m>>k;
int maxn=0;
for(int i=1;i<=n;i++){
int t,c;
cin>>t>>c;
maxn=max(maxn,t);
m1[t]+=c;
}
for(int i=maxn;i>=k;i--){
if(m<m1[i]){
cout<<i<<endl;
return ;
}
else{
m-=m1[i];
m1[i-1]+=m1[i];//所有最大天数减一，则减一的天数要加上之前最大天数的数量
}
}
cout<<k<<endl;
return ;
}
int main(){
int t;
// cin>>t;
t=1;
while(t--){
solve();
}
return 0;
}
二分做法：
因为最小天数必须是k，则我们二分的时候就可以将k作为l的值，r的值即为所有垦田当中最大的天数。之后进行二分即可。这里可以用排序进行一个简单的优化，就是说我们在二分到mid天时候，如果后面垦田的天数本身比mid小，就不需要再判断了。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+10;
int n,m,k;
struct node
{
int t,c;
}a[N];
bool cmp(node a,node b){
if(a.t==b.t){
return a.c>b.c;
}
else{
return a.t>b.t;
}
}
bool check(int x){
ll ans=0;
for(int i=1;i<=n;i++){
if(x>=a[i].t){
break;
}
else{
ans+=a[i].c*(a[i].t-x);
}
}
if(ans<=m){
return true;
}
else{
return false;
}
}
void solve(){
// int n,m,k;
cin>>n>>m>>k;
int l=k;//最少得是k天
int r=0;
for(int i=1;i<=n;i++){
int t,c;
cin>>t>>c;
r=max(t,r);
a[i]={t,c};
}
sort(a+1,a+n+1,cmp);
while(l<r){
int mid=(l+r)/2;
if(check(mid)){
r=mid;
}
else{
l=mid+1;
}
}
cout<<l<<endl;
return ;
}
int main(){
int t1;
// cin>>t;
t1=1;
while(t1--){
solve();
}
return 0;
}
C题CCC单词搜索
具体问题
给定一个 R×C的大写字母矩阵。
请你在其中寻找目标单词 W。
已知，目标单词 W由若干个不同的大写字母构成。
目标单词可以遵循以下两种规则，出现在矩阵的水平、垂直或斜 45度线段中：
单词出现在一条线段上。
单词出现在两条相互垂直且存在公共端点的线段上。也就是说，单词首先出现在某线段上，直到某个字母后，转向 90度，其余部分出现在另一条线段上。
具体可以参照图例。
请你计算，目标单词在给定矩阵中一共出现了多少次。
C思路:
可以看出这是一个dfs的搜索问题，我们可以枚举八个方向，因为他说斜着也是可以的，然而这个题也是一个比较特殊的题，就是我们可以90度变换一次方向（仅限一次），也就是一个单词在两条直线上，所以我们也可以为这个开一个标记，表示一条方向上搜索一次，转弯搜索一次。
C代码：
#include<bits/stdc++.h>
using namespace std;
const int N = 110;
char s[N][N];
string w;
int n, m;
int res;
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
int ix[4] = {-1, -1, 1, 1}, iy[4] = {-1, 1, 1, -1};
void dfs(int x, int y, int t, int f, int d, int k){
if(t == w.size() - 1 && k < 2){ //题目中要求两个线段或一个线段，即k<2
res ++;
return;
}
if(f == -1){ //竖直水平方向搜索
for(int i = 0; i < 4; i ++){
int a = x + dx[i], b = y + dy[i];
if(a < 0 || a >= n || b < 0 || b >= m) continue;
if(s[a][b] == w[t + 1]){
if(t != 0 && i != d)dfs(a, b, t + 1, -1, i, k + 1); //需转弯的情况
else dfs(a, b, t + 1, -1, i, k); //搜索第一次或者没转弯的情况
}
}
}
if(f == 1){ //斜着方向搜索 原理同上
for(int i = 0; i < 4; i ++){
int a = x + ix[i], b = y + iy[i];
if(a < 0 || a >= n || b < 0 || b >= m) continue;
if(s[a][b] == w[t + 1]){
if(t != 0 && i != d)dfs(a, b, t + 1, 1, i, k + 1);
else dfs(a, b, t + 1, 1, i, k);
}
}
}
}
int main(){
cin >> w;
cin >> n >> m;
for(int i = 0; i < n; i ++)
for(int j = 0; j < m; j ++)
cin >> s[i][j];
for(int i = 0; i < n; i ++){
for(int j = 0; j < m; j ++)
if(s[i][j] == w[0]){
//进行两种搜索方式
dfs(i, j, 0, -1, 0, 0);
dfs(i, j, 0, 1, 0, 0);
}
}
cout << res << endl;
return 0;
}
D对称山脉
有 N座山排成一排，从左到右依次编号为 1∼N。
其中，第 i座山的高度为 hi。对于一段连续的山脉，我们使用如下方法定义该段山脉的不对称值。如果一段连续的山脉由第 l∼r（1≤l≤r≤N）座山组成，那么该段山脉的不对称值为
现在，你需要回答 N个问题，问题编号 1∼N。
其中，第 i个问题的内容是：请计算，一段恰好包含 i座山的连续山脉（即长度为 i的连续区间）的不对称值的最小可能值。
D思路：
这是一个比较明显的dp问题，我们要找的是连续i座山脉的不对称值的最小可能值。因此我们就可以做一个二维背包的转换，因此我们可以得到一个状态转移方程式(端点对称之差加上除去端点的dp背包)
这是我们简单的状态转移方程式，但是实际上我们需要在程序中稍微变一下型。
D代码
#include<bits/stdc++.h>
using namespace std;
const int N=5010;
int a[N];
int dp[N][N];
int ans[N];
void solve(){
int n;
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
}
memset(ans,0x3f,sizeof ans);
for(int j=2;j<=n;j++){
for(int i=1;i<=n-j+1;i++){
dp[i][i+j-1]=abs(a[i]-a[i+j-1])+dp[i+1][i+j-2];
ans[j]=min(ans[j],dp[i][j+i-1]);
}
}
ans[1]=0;
for(int i=1;i<=n;i++){
cout<<ans[i]<<" ";
}
cout<<endl;
return ;
}
int main(){
int t;
t=1;
while(t--){
solve();
}
return 0;
}
E所有三角形
题目链接具体信息请结合原出题地址查看。
建筑商波奇刚刚完成了她的最新作品：一条精美的巷道。
此巷道由两排瓷砖组成，每排都恰好包含 C个边长为 1的白色等边三角形瓷砖。
其中，上排左起第一个三角形瓷砖指向上方，每对相邻三角形瓷砖（即包含公共边的三角形瓷砖）的指向都相反（可参照图例）。
不幸的是，她不小心打翻了一桶黑色油漆，使得其中一些三角形瓷砖被染黑了。
由于被染黑的瓷砖油漆未干，她计划使用胶带将所有染黑区域的边缘围住，以防别人误踩。
请你计算，她需要使用多少米的胶带。
输入格式
第一行包含整数 C。
第二行包含 C个整数 0或 1，表示第一排每个瓷砖的颜色。如果第 i个整数为 1，则表示第 i个瓷砖（左起）为黑色，如果第 i个整数为 0，则表示第 i个瓷砖（左起）为白色。
第三行包含 C个整数 0或 1，表示第二排每个瓷砖的颜色。如果第 i个整数为 1，则表示第 i个瓷砖（左起）为黑色，如果第 i个整数为 0，则表示第 i个瓷砖（左起）为白色。
E思路：
这个就是铺瓷砖的方式，因为我们需要把变黑的瓷砖圈起来，因此我们只需要看一个黑色区域中每个三角形贡献出几条边就可以。只需要简单的模拟一下就可以了。
E代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+10;
int a[3][N];
void solve(){
int c;
cin>>c;
for(int i=1;i<=2;i++){
for(int j=1;j<=c;j++){
cin>>a[i][j];
}
}
int ans=0;
for(int i=1;i<=c;i++){
if(!a[1][i]){
continue;
}
int cnt=3;
if(i%2){
if(a[2][i]){
cnt--;
}
}
if(a[1][i-1]){
cnt--;
}
if(a[1][i+1]){
cnt--;
}
ans+=cnt;
}
for(int i=1;i<=c;i++){
if(!a[2][i]){
continue;
}
int cnt=3;
if(i%2){
if(a[1][i]){
cnt--;
}
}
if(a[2][i-1]){
cnt--;
}
if(a[2][i+1]){
cnt--;
}
ans+=cnt;
}
cout<<ans<<endl;
}
int main(){
int t;
t=1;
while(t--){
solve();
}
return 0;
}