复习Day2

4.全球变暖 - 蓝桥云课 (lanqiao.cn)

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e3+6;
char a[N][N];
int n;
int xx[]={0,1,-1,0};//右 下 上 左
int yy[]={1,0,0,-1};
int scc=0;//涂色器
int clsm[N*N];//用于存储每个颜色是否还有剩余
int col[N][N];//表示每个岛屿的颜色
int ans;
void dfs(int x,int y){//是一个涂色的过程
    col[x][y]=scc;//先给这个小岛涂上色
    for(int i=0;i<4;i++){
        int tx=x+xx[i];
        int ty=y+yy[i];
    if(tx<1||ty<1||tx>n||ty>n)continue;//出界要跳
    if(a[tx][ty]=='.')continue;//是海洋要跳
    if(col[tx][ty])continue;//被染色过要跳
    dfs(tx,ty);
    }
    return ;
}
signed main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            cin>>a[i][j];
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(a[i][j]!='.'&&!col[i][j]){//找到了一个没有涂色的 岛
                scc++;//换一种颜色
                dfs(i,j);
            }
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(a[i][j]=='.')continue;//如果是海洋就不行
            bool tag=1;
            for(int k=0;k<4;k++){
                int tx=i+xx[k];
                int ty=j+yy[k];
                if(a[tx][ty]=='.')tag=0;//四个角有一个是海洋就不行
            }
            if(tag){//找完四个角后说明有岛屿剩余了
            if(!clsm[col[i][j]]){ans++;//存活的岛屿++
            clsm[col[i][j]]=1;//设为已经存过了
            }
        }
    }
}
    cout<<scc-ans;
    return 0;
}

最大公约数__gcd(a,b) 最小公倍数a*b/__gcd(a,b)

0摆花 - 蓝桥云课 (lanqiao.cn)

#include<bits/stdc++.h>
const int N=105;
using namespace std;
int a[N];
int dp[N][N];//dp[i][j]表示前i种花 共摆了j盆
int p=1e6+7;
int main(){
    memset(dp,0,sizeof dp);
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>a[i];
    dp[0][0]=1;

    for(int i=1;i<=n;i++){
        for(int j=0;j<=m;j++){//前i种花摆了j盆
            for(int k=0;k<=a[i]&&k<=j;k++){//第i种花摆了k盆
//要保证第i种花摆的盆数小于等于花数a[i] 小于等于一共摆的数j
                dp[i][j]=(dp[i][j]+dp[i-1][j-k])%p;
//前i-1种花排了j-k盆
//dp[i][j]表示前i种花拍了j盆的方案数 就是
// 第i种花摆了 0,1,2,3,4....盆 前i-1种花摆了j-0,j-1,j-2,j-3,j-4....盆
//的和
            }
        }
    }
    cout<<dp[n][m]%p;
    return 0;
}

0跳石头 - 蓝桥云课 (lanqiao.cn)

#include <bits/stdc++.h>
using namespace std;
const int N=5e4+7;
int l,n,m;
int stones[N];
bool check(int mid){//最短跳跃距离
  int pos=0;//记录目前在哪个石头上目前在起点石头上
  int cnt=0;//搬走多少个石头
  for (int i = 1; i <= m+1; i++)
        if (stones[i] - stones[pos] < mid)
            cnt++;//小于最小跳跃距离就搬走石头i然后去看下一个石头
        else pos = i;//否则跳上
    if (cnt <= n) return true;//最短跳远距离mid还可以更大
    return false;
}
void solve(){
  cin>>l>>m>>n;//起点到终点的距离 岩石数 至多移走
  for(int i=1;i<=m;i++){
    cin>>stones[i];//表示第i个石头到起点stones[0]的距离
  }
  stones[m+1]=l;//终点石头
  int l=1,r=1e9+7;//最短的跳远距离
  while(l<r){
    int mid=(l+r+1)>>1;
    if(check(mid))l=mid;
    else r=mid-1;
  }
  cout<<l;
  return ;
}
int main(){
  int t=1;
  while(t--)solve();
  return 0;
}

对a[i]不断进行|运算可以不断更新组合

0糖果 - 蓝桥云课 (lanqiao.cn)

#include <bits/stdc++.h>
using namespace std;
const int maxn=2e6;
int dp[maxn];
//dp[i]表示获得组合i(i用二进制表示,0为未获得,1为已获得)需要购买多少包糖果
//M最大可达20,化为二进制为2^20,需要开大约为2e6的数组 
int a[maxn];

int main(){
    int N,M,K;cin>>N>>M>>K;
    int n=(1<<M)-1;//若获得全部种类的糖果，二进制表示为11...111(M个1) 
    for(int i=1;i<maxn;i++)dp[i]=0x3f3f3f3f;//dp数组初始化为极大值 
    
    for(int i=0;i<N;i++){//输入N包糖果的信息 
        for(int j=0;j<K;j++){//输入每包糖果的K个口味
            int tmp;
            cin>>tmp;
            a[i]=a[i]|(1<<(tmp-1));//1主导 有1则1
            //如tmp分别为1,3,5,则经过如上处理后a[i]的二进制为10101(重点)   
        } 
        dp[a[i]]=1;//获得a[i]组合,只需要购买当前糖果(1包)即可 
    }
    dp[0]=0;//不获取任何组合的糖果,无需购买
    
    for(int i=0;i<N;i++){//枚举N包糖果 
        for(int j=1;j<n;j++){//枚举所有的糖果组合，为二进制00...001~11.111 
            //购买当前的糖果a[i],获得糖果组合为当前的j对a[i]做或运算,使得j的一些0位变成1
            //此种做法需要购买dp[j]+1包糖果,得到j|a[i]的糖果组合 
            //若原来的dp[j|a[i]]大于dp[j]+1,说明后者更优,则用dp[j]+1更新之 
            dp[j|a[i]]=min(dp[j|a[i]],dp[j]+1);
        }
    }
    if(dp[n]<=N)cout<<dp[n]<<'\n';//能获得全部的糖果种类 
    else cout<<-1<<'\n';//不能获得全部的糖果种类 
    return 0;
}

788. 逆序对的数量 - AcWing题库

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+7;
int n;
int a[N],tmp[N];
int  merge_sort(int q[],int l,int r){
	int ans=0;
	//1.结束条件 
	if(l>=r)return 0;
	//2.分解为子问题 
	int mid=l+(r-l)/2;
	ans+=merge_sort(q,l,mid)+merge_sort(q,mid+1,r);
	
	//3.对于每一个子问题 
	int k=0,i=l,j=mid+1;
	while(i<=mid&&j<=r){
		if(q[i]<=q[j])tmp[k++]=q[i++]; //用第一个数组的 
		else {
		tmp[k++]=q[j++];//如果右边的的更小就用右边的的
		 //此时两个数组都是有序的了 升序的
		 // 4 6 7        5    6     9 
		// i   mid     mid+1       r
		//比右边这个数大的右mid-i+1个都形成逆序对 
      	ans+=mid-i+1;
	}
}
//4.扫尾
	while(i<=mid)tmp[k++]=q[i++];
	while(j<=r)tmp[k++]=q[j++];
	//5.还原一个子问题的区间l,r 
	for(i=l,j=0;i<=r;i++,j++)q[i]=tmp[j]; 
	return ans;
}
void solve(){
	cin>>n;
	for(int i=0;i<n;i++)cin>>a[i];
	cout<<merge_sort(a,0,n-1);
}
signed main(){
	int t=1;
	while(t--)solve();
	return 0;
}

1241. 外卖店优先级 - AcWing题库

#include <bits/stdc++.h>
using namespace std;
#define int long long
int dd[10002][10002];//存储i时刻，j号店，有多少订单；
bool st[10002];//存储j号店是否在优先缓存中
int score[10002];//存储j号店的优先级
signed main(){
    int N,M,T;cin>>N>>M>>T;
    while(M--){
        int ts,id;
        cin>>ts>>id;
        dd[ts][id]++;
    }
    for(int i=1;i<=T;i++)//遍历每一个时刻的每一家店
      for(int j=1;j<=N;j++){
            if(dd[i][j]>0)//如果i时刻j号店有订单
            {
                score[j]+=2*dd[i][j];//每有一单优先级加 2,直接2*订单数
            }else{//如果外卖店没有订单，则优先级会减少 1,最低减到 0
                if(score[j]-1>=0)score[j]--;
            }
            if(score[j]>5)st[j]=true;
            if(score[j]<=3)st[j]=false;
        }
    int res=0;
    for(int i=1;i<=N;i++)//遍历每一家店，如果在优先缓存中，res+1,否则res+0;
    res+=st[i];
    cout<<res;
    return 0;
}