总结:暴力可以拿不少分
后面的暴力多数都是dfs暴力,可以多往这方面想想
日期统计(暴力枚举)
#include <bits/stdc++.h>
using namespace std;
int main(){
int ans = 0;
int arr[] = {5, 6, 8, 6, 9, 1, 6, 1, 2, 4, 9, 1, 9, 8, 2, 3, 6, 4, 7, 7, 5, 9, 5, 0, 3, 8, 7, 5, 8, 1, 5, 8, 6, 1, 8, 3, 0, 3, 7, 9, 2, 7, 0, 5, 8, 8, 5, 7, 0, 9, 9, 1, 9, 4, 4, 6, 8, 6, 3, 3, 8, 5, 1, 6, 3, 4, 6, 7, 0, 7, 8, 2, 7, 6, 8, 9, 5, 6, 5, 6, 1, 4, 0, 1, 0, 0, 9, 4, 8, 0, 9, 1, 2, 8, 5, 0, 2, 5, 3, 3 };
int month[] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
for(int i = 1;i <= 12;i++){
for(int j = 1; j <= month[i];j++){
int data[] = {2,0,2,3,i/10,i%10,j/10,j%10};
int k = 0;
for(int i = 0;i < 100;i++){
if(arr[i] == data[k]){
k++;
if(k == 8){
ans++;
}
}
}
}
}
cout << ans << endl;
}
01串的熵(枚举)
#include <iostream>
#include <cmath>
using namespace std;
int main()
{
double n = 23333333;
double s = 11625907.5798;
for(int a = 0; a<= n;a++){
int b = n - a;
if(a >= b) continue;
double ans = -1.0 * b / n * b * log2(b/n) - 1.0 * a /n * a *log2(a/n);
if(fabs(ans-s) < 1e-4){
cout << a << endl;
}
}
return 0;
}
冶炼金属(枚举。。)
·
·
·
飞机降落(dfs枚举)
由于数据很小,优先考虑dfs枚举的做法
#include <bits/stdc++.h>
using namespace std;
const int N = 11;
int n;
bool st[N];
struct plane{//这里值得学习,刚看见这题的时候考虑过开三个数组,显然不如结构体简洁
int t,d,l;
}p[N];
bool dfs(int u,int last){
if(u >= n) return true;//如果当前遍历的个数大于了n说明存在可行的方案了直接返回
for(int i = 0;i < n;i++){
if(!st[i] && p[i].t + p[i].d >= last){//必须是当前飞机没有遍历过且,当前飞机的最晚降落时间比上一个最早的降落时间晚
st[i] = true;//记录当前飞机已经进入了dfs
if(dfs(u+1,max(last,p[i].t)+p[i].l)) return true;//从上一个飞机的降落时间和当前飞机的盘旋时间找一个最大值,再加上降落所需的时间就是最早降落时间
st[i] = false;//重置
}
}
return false;//如果没有一个符合,就返回false
}
void solve(){
memset(st,0,sizeof st);//每次重新读入数据记得把st数组重置
cin >> n;//输入数据数量
for(int i = 0;i < n;i++){
cin >> p[i].t >> p[i].d >> p[i].l;
}
if(dfs(0,0))cout << "YES" << endl;//如果存在可行方案就yes
else cout << "NO" << endl;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int T;
cin >> T;
while(T--){
solve();
}
return 0;
}
接龙数列(正解:Dp,暴力dfs)
这道题暴力就是通过dfs找出所有可能的情况,并判断是否合法
dp则是通过简化找出所有情况的可能,针对性的进行寻找
//正解DP
#include <bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
#define endl '\n';
const int N = 1e5+10;
int a[N];
int f[N][15];
int num_begin(int x){
int res = 0;
while(x){
res = x % 10;
x/=10;
}
return res;
}
int num_end(int x){
return (x % 10);
}
int main(){
memset(f,INF,sizeof f);//将f初始化为无穷大
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n;
cin >> n;
for(int i = 1;i <= n;i++){
cin >> a[i];//读入数组
}
//f[i][j]表示已经取了i个数且最后一个数的结尾是j的情况最少删除几个数
for(int i = 0;i < 10;i++){
f[0][i] = 0; //取0时不管j是多少都是0
}
for(int i = 1;i <= n;i++){
for(int j = 0;j < 10;j++){
f[i][j] = f[i-1][j]+1;//如果删除的话,就是上一个数加一
}
int final = num_end(a[i]);//如果不删的话取出这一个数的结尾
int first = num_begin(a[i]);//再取出这一个数的开头
f[i][final] = min(f[i-1][first],f[i][final]);//取出i个时,以final结尾的最优解是:上一个以当前的开头结尾的最优解和当前已有的最优解进行比较
}
int ans = INF;//初始化答案为无穷大
for(int i = 0; i < 10;i++){//因为结尾无非0~9,所以直接遍历所有f[n][i]即可,找出最小的就是最优解
ans = min(ans,f[n][i]);
}
cout << ans << endl;
}
//暴力DFS
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
int a[N];
int n;
int ans;
//0 1 2 3
//3 1 2
//2 1
//1 0
int num_begin(int x){//求数的开头
int res = 0;
while(x){
res = x % 10;
x/=10;
}
return res;
}
int num_end(int x){//求数的结尾
return (x % 10);
}
//u是当前的个数,cnt是接龙数列的长度,last是当前前一个数列的末尾值
void dfs(int u,int cnt,int last){
if(u >= n){//如果遍历完了n,输出最大的可能数列
ans = max(ans,cnt);
return;
}
if(n - u + cnt <= ans) return;//如果当前加上待接龙的也比ans小,那么没必要继续dfs
if(last == -1 || num_end(last) == num_begin(a[u])){//如果可以接龙,那么接龙
dfs(u+1,cnt+1,a[u]);
}
dfs(u+1,cnt,last);//在尝试一下不接龙
}
int main(){
cin >> n;
for(int i = 0;i < n;i++){
cin >> a[i];
}
dfs(0,0,-1);//通过dfs找出所有可能的方案
cout << n - ans << endl;//n-ans是需要删除的个数
}
岛屿个数(图论,BFS/DFS)
根据题意将这个题转化为图的遍历
假设岛围起来的海叫内海,那么外面的海就是外海,对外海进行bfs遍历,期间接触到的岛,都标记一下(标记时对岛进行遍历,保证这个岛的各个地方不会二次标记)。标记个数就是岛的个数
特例是当没有外海时,说明全部被一个大岛围起来了,最终岛的数量为1
#include <bits/stdc++.h>
using namespace std;
const int N = 100;
bool st_sea[N][N];
bool st_land[N][N];
int g[N][N];//记录图
int n,m;
int dx[8] = {-1,-1,-1,0,1,1,1,0};//方向向量
int dy[8] = {-1,0,1,1,1,0,-1,-1};
int ddx[4] = {-1,0,1,0};
int ddy[4] = {0,1,0,-1};
int ans = 0;
bool check(int x,int y){//判断边界条件
return (x >= 0 && x < n && y >= 0 && y < m);
}
void bfs_land(int x,int y){//广搜找相连的陆地
st_land[x][y] = true;
queue<pair<int,int>> q;
q.push({x,y});
while(q.size()){
auto t = q.front();
q.pop();
for(int i = 0;i < 4;i++){
int nx = t.first + ddx[i];
int ny = t.second + ddy[i];
if(check(nx,ny) && g[nx][ny] && !st_land[nx][ny]){
st_land[nx][ny] = true;
q.push({nx,ny});
}
}
}
}
void bfs_sea(int x,int y){//广搜找外海周围的陆地
queue<pair<int,int>> q;
st_sea[x][y] = true;
q.push({x,y});
while(q.size()){
auto t = q.front();
q.pop();
for(int i = 0;i < 8;i++){
int nx = t.first + dx[i];
int ny = t.second + dy[i];
if(check(nx,ny) && !g[nx][ny] && !st_sea[nx][ny]){
st_sea[nx][ny]=true;
q.push({nx,ny});
}
if(check(nx,ny) && g[nx][ny] && !st_land[nx][ny]){
ans++;
bfs_land(nx,ny);
}
}
}
}
void solve(){
cin >> n >> m;
ans = 0;
for(int i = 0;i <= n;i++){
for(int j = 0;j <= m;j++){
st_sea[i][j] = st_land[i][j] = false;
}
}
for(int i = 0;i < n;i++){
string s;cin>>s;
for(int j = 0;j < m;j++){
g[i][j] = s[j] - '0';
}
}
bool flag = false;
for(int i = 0;i < n;i++){
for(int j = 0;j < m;j++){
if(!i || i == n - 1 || !j || j == m - 1){
if(!g[i][j] && !st_sea[i][j]){
flag = true;
bfs_sea(i,j);
}
}
}
}
if(!flag){//如果没有外海,说明这个图被陆地给包裹了,直接输出1
ans = 1;
}
cout << ans << endl;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int T;
cin >> T;
while(T--){
solve();
}
return 0;
}
子串简写(暴力/二分)
通过双指针暴力可以拿70%
但是二分优化以后能拿全部
具体原理是,从头遍历,遇到c1,就存入队列,遇到c2就清算队列中可能存在的组合,这里用二分快速查找队列中符合条件的那个值,符合条件的那个值的左边所有值都符合条件,可以快速统计
//正解:二分
#include <bits/stdc++.h>
#define int long long
using namespace std;
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int k;
cin >> k;
int ans = 0;
vector<int> pc1;
string s;
char c1,c2;
cin >> s >> c1 >> c2;
for(int i = 0;i < s.size();i++){
if(s[i]==c1){//遇到c1加入队列
pc1.push_back(i);
}
if(s[i]==c2){//遇到c2清算
if(i-k+1 < 0 || !pc1.size()){//如果当前还未达到k的要求,或者是还没找到过c1就跳出
continue;
}
int l = 0,r = (int)pc1.size() - 1;//进行二分
while(l < r){
int mid = l + r + 1 >> 1;//防止死循环
if(pc1[mid] <= (i - k + 1)){
l = mid;
}else{
r = mid - 1;
}
}
if(pc1[l] <= i - k + 1){
ans += (l + 1);//答案累加
}
}
}
cout << ans << endl;
}
//暴力做法 (双指针)
#include <iostream>
using namespace std;
int main(){
int k;
cin >> k;
string s;
cin >> s;
char c1,c2;
cin >> c1 >> c2;
int ans = 0;
for(int i = 0;i < s.size();i++){
if(s[i] == c1){
for(int j = i + k - 1;j < s.size();j++){
if(s[j] == c2) ans++;
}
}
}
cout << ans << endl;
}
整数删除(暴力枚举/双向链表+堆排序)
暴力枚举就是不断遍历数组找出最小值并删除最小值将最小值旁边的两个数累加
可以用st数组来表示数是否呗删除
正解就是对暴力的优化,通过堆排序循序找出最小值,通过双向链表迅速删除一个值
//正解:堆+链表
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
const int N = 500010;
long long cnt[N];
int st[N],ne[N],pre[N];
int main(){
int n,k;
cin >> n >> k;
priority_queue<pair<long long,int>,vector<pair<long long ,int >>,greater<pair<long long,int>> > q;
for(int i = 1;i <= n;i++){//初始化链表
long long v;
cin >> v;
q.push({v,i});
pre[i] = i - 1;
ne[i]= i + 1;
}
int g = n - k;//计算出最终堆中的元素数量
while(q.size() > g){
auto p = q.top();//取出堆顶
q.pop();
long long v = p.first,ix = p.second;//v是堆顶的值,ix是堆顶的下标
if(cnt[ix]){//如果这个堆顶需要加上某个值就回炉重造
q.push({v+cnt[ix],ix});
cnt[ix] = 0;//加完了置0
}else{
int l = pre[ix],r = ne[ix];//将该堆顶的左右元素取出
st[ix] = 1;//表示已经被删除了
cnt[l] += v;//左右两点加上堆顶的值
cnt[r] += v;
ne[l] = r;//左右两点相连
pre[r] = l;
}
}
vector<long long> a(n+1);//开一个数组记录最终的答案
for(int i = 0;i < g;++i){
auto p = q.top();
q.pop();
a[p.second] = p.first+cnt[p.second];//以防还有值没加上
}
for(int i =1;i <= n;++i){
if(!st[i]) cout << a[i] << " ";//从头遍历数组如果未被删除就输出
}
}
////暴力做法
#include <bits/stdc++.h>
using namespace std;
const int N = 5e5+10;
bool st[N];
int a[N];
int main(){
int n,k;
cin >> n >> k;
for(int i = 1;i <= n;i++){
cin >> a[i];
}
while(k--){
int mi = 0x3f3f3f3f;
int pos = -1;
for(int i = 1;i <= n;i++){
if(mi > a[i] && !st[i]){
mi = a[i];
pos = i;
}
}
st[pos]=true;
for(int i = pos - 1;i >= 0;i--){
if(!st[i]){
a[i]+=mi;
break;
}
}
for(int i = pos + 1;i <= n;i++){
if(!st[i]){
a[i]+=mi;
break;
}
}
}
for(int i = 1;i <= n;i++){
if(!st[i]){
cout << a[i] <<" ";
}
}
return 0;
}