首页 > 其他分享 >Acwing. 秋季每日一题

Acwing. 秋季每日一题

时间:2023-08-28 19:55:49浏览次数:45  
标签:秋季 开垦 int 每日 dfs 单词 线段 dp 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取决于耗时最长的区域,即:

\[Ttoal=max(t1,t2,t3.....) \]

为了加快开垦进度,顿顿准备在部分区域投入额外资源来缩短开垦时间。
具体来说:
在第 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)座山组成,那么该段山脉的不对称值为

\[∑|hl+i−hr−i|(0≤i≤(r−l)/2) \]

现在,你需要回答 N个问题,问题编号 1∼N。
其中,第 i个问题的内容是:请计算,一段恰好包含 i座山的连续山脉(即长度为 i的连续区间)的不对称值的最小可能值。

D思路:

这是一个比较明显的dp问题,我们要找的是连续i座山脉的不对称值的最小可能值。因此我们就可以做一个二维背包的转换,因此我们可以得到一个状态转移方程式(端点对称之差加上除去端点的dp背包)

\[dp[i][j]=abs(a[i+j-1]-a[i])+dp[i+1][j-1]; \]

这是我们简单的状态转移方程式,但是实际上我们需要在程序中稍微变一下型。

\[dp[i][i+j-1]=abs(a[i]-a[i+j-1])+dp[i+1][i+j-2]; \]

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;
}

标签:秋季,开垦,int,每日,dfs,单词,线段,dp,Acwing
From: https://www.cnblogs.com/du463/p/17663262.html

相关文章

  • Acwing. 第 118 场周赛
    Acwing.第118场周赛比赛链接这几天开学了,一直在宿舍歇着来着,从下周一开始就要开始加训了!!!A题循环串:给定两个整数n,a,请你用前a个小写字母为循环节,构成一个无限长的循环字符串,然后输出该字符串的前n个字符。例如,当a=2时,循环字符串为ababab...,当a=3时,循环字符串为......
  • AcWing 875. 快速幂
    题目给定$n$组$a_i,b_i,p_i$,对于每组数据,求出${a_i}^{b_i}mod{p_i}$的值。输入格式第一行包含整数$n$。接下来$n$行,每行包含三个整数$a_i,b_i,p_i$。输出格式对于每组数据,输出一个结果,表示${a_i}^{b_i}mod{p_i}$的值。每个结果占一行。数据范围$1≤n≤100000,......
  • AcWing 873. 欧拉函数
    题目给定$n$个正整数$a_i$,请你求出每个数的欧拉函数。欧拉函数的定义$1∼N$中与$N$互质的数的个数被称为欧拉函数,记为$\varphi(N)$。若在算数基本定理中,$N={p_1}^{a_1}{p_2}^{a_2}...{p_m}^{a_m}$,则:$\varphi(n)=m(1-1/p_1)(1-1/p_2)...(1-1/p_k)$输入格式第......
  • 罗勇军老师每日一题系列
    罗勇军老师每日一题系列罗老师有专门的题解,这里只是个人的做题总结。罗老师的QQ群,930175362罗老师博客1.最小区间有n头奶牛,奶牛有位置\(P[i]\)和类别\(T[i]\)两种属性,求能够包含所有类别的奶牛的最小区间的长度。\(1<=n<=5e4,P[i],T[i]<=1e9\)题解二分答案。......
  • 大厂算法每日总结(统计文件夹下的文件)
    //统计文件夹下的文件,是文件就累计1,隐藏文件空累计,文件不累计publicstaticvoidmain(String[]args){System.out.println(getFileNumber("D:\重要文件"));}publicstaticintgetFileNumber(StringfolderPath){Fileroot=newFile(folderPath);if(!root.isDirectory(......
  • 大厂算法题每日总结(num最近的,2的某次方)
    //给定一个非负整数num,不用循环,返回>=num,并离num最近的,2的某次方publicstaticfinalinttableSizeFor(intn){n--;n|=n>>>1;//>>>不带符号右移n|=n>>>2;n|=n>>>4;n|=n>>>8;n|=n>>>16;//打满,至此int32位,全打满return(n<0......
  • 大厂算法每日总结(GB字符串至少交换几次)
    //一个数组中只有两种字符'G'和'B',//想要所有的G都放左边,所有的B都放右边或者所有的B都放左边,所有的G都放右边//但只能在相邻字符之间进行交换操作//返回至少需要交换几次//方法1publicstaticintminSteps1(Strings){if(s==null||s.equals("")){return0;}......
  • 大厂算法题每日总结(绳子最大能盖的数组节点)
    //绳子最大能盖的数组节点publicstaticvoidmain(String[]args){int[]arr={1,4,7,9,60};System.out.println(maxPoint2(arr,50));}publicstaticintmaxPoint(int[]arr,intL){//L是绳子的长度 intres=1; for(inti=0;i<arr.length;i++){ intnearest=n......
  • 每日一库:fsnotify简介
    fsnotify是一个用Go编写的文件系统通知库。它提供了一种观察文件系统变化的机制,例如文件的创建、修改、删除、重命名和权限修改。它使用特定平台的事件通知API,例如Linux上的inotify,macOS上的FSEvents,以及Windows上的ReadDirectoryChangesW。fsnotify具有以下特点:跨平台支持:fs......
  • AcWing 872. 最大公约数
    题目给定$n$对正整数$a_i,b_i$,请你求出每对数的最大公约数。输入格式第一行包含整数$n$。接下来$n$行,每行包含一个整数对$a_i,b_i$。输出格式输出共$n$行,每行输出一个整数对的最大公约数。数据范围$1≤n≤10^5,1≤a_i,b_i≤2×10^9$输入样例:23646输出样......