1231. 航班时间 - AcWing题库
#include<bits/stdc++.h>
using namespace std;
int getTime(){//得到时间
int h1,m1,s1,h2,m2,s2,d=0;
scanf("%d:%d:%d %d:%d:%d (+%d)",&h1,&m1,&s1,&h2,&m2,&s2,&d);
//补匹配直接跳过
int time=d*24*3600 +h2*3600+m2*60+s2-(h1*3600+m1*60+s1);
return time;
}
int main()
{
int t;
scanf("%d",&t);
for(int i = 0; i < t; i++)
{
int time1=getTime();
int time2=getTime();
int t=(time1+time2)/2;
printf("%02d:%02d:%02d\n", t/3600, t/60%60, t%60);
}
return 0;
}1264. 动态求连续区间和 - AcWing题库
#include <bits/stdc++.h>
using namespace std;
const int N=100010;
int a[N],tr[N];
int n,m;
int lowbit(int x){
return x&-x;
}
//修改值的时候 自下向上
int add(int x,int v){
for(int i=x;i<=n;i+=lowbit(i))tr[i]+=v;
}
//求和的时候 自上而下
int query(int x){//前缀和思想
int res=0;
for(int i=x;i>0;i-=lowbit(i))res+=tr[i];//注意这里是>0 树状数组下标从1开始
return res;
}
void solve(){
cin>>n>>m;
for(int i=1;i<=n;i++)cin>>a[i];
for(int i=1;i<=n;i++)add(i,a[i]);
// 表示第 i个数加上a[i]
while(m--){
int k,a,b;cin>>k>>a>>b;
if(k==1)add(a,b);//第a个数加上b
else cout<<query(b)-query(a-1)<<'\n';
}
return ;
}
int main(){
int t=1;
while(t--)solve();
return 0;
}13.数字三角形 - 蓝桥云课 (lanqiao.cn)
#include <bits/stdc++.h>
using namespace std;
const int N=106;
int a[N][N];
int n;//垂直往下走和往右下走的次数相差不超过1
int dp[N][N][N];//dp[i][j][k]表示的是z走到(i,j)已经向右下走了k次 目前的和
int main(){
cin>>n;
for(int i=1;i<=n;i++){
for(int j=1;j<=i;j++){
cin>>a[i][j];
}
}
// dp[1][1][]=a[1][j];
for(int i=1;i<=n;i++)dp[n][i][0]=a[n][i];//走回(1,1)点
for(int i=n-1;i>=1;i--){//枚举后i行
for(int j=1;j<=i;j++){//因为是从i+1行转移过来的 所以要倒着枚举
for(int k=0;k<=n-i;k++){//枚举已经向右下走了k次
if(k>=1)dp[i][j][k]=a[i][j]+max(dp[i+1][j][k],dp[i+1][j+1][k-1]);
else dp[i][j][k]=a[i][j]+dp[i+1][j][k];}
}
}
if((n-1)%2==0)cout<<dp[1][1][(n-1)/2];//如果要走偶数次 那么就一定是(n-1)/2
else cout<<max(dp[1][1][(n-1)/2],dp[1][1][(n-1)/2+1]);
return 0;
}14.机器翻译 - 蓝桥云课 (lanqiao.cn)
#include <bits/stdc++.h>
using namespace std;
const int N=1006;
int m,n;//内存容量 文章长度
int q[N],hh=1,tt=0;//模拟队列
int main(){
cin>>m>>n;
int ans=0;
for(int i=1;i<=n;i++){
int num;cin>>num;
bool tag=0;//在内存中无匹配
for(int j=hh;j<=tt;j++){//数组实现的队列可以遍历
if(q[j]==num)tag=true;
}//找到了内存中有这个
// if(find(q+hh,q+tt+1,num)!=q+tt+1)tag=1;//必须是q+tt+1不能不写
if(tag)continue;//如果匹配到了就跳
if(tt-hh+1==m)hh++;//没有匹配到且满内存了,队头出队
q[++tt]=num;//队尾加元素
ans++;
}
cout<<ans<<'\n';
return 0;
}16.谈判 - 蓝桥云课 (lanqiao.cn)
#include <bits/stdc++.h>
using namespace std;
const int N=1002;
typedef long long ll;
int main(){
priority_queue<ll,vector<ll>,greater<int> >pq;
//默认less排序 top在右 less在左
int n;cin>>n;
while(n--){
int m;cin>>m;pq.push(m);
}
ll sum=0;
while(pq.size()!=1){
ll total=0;
total+=pq.top();pq.pop();
total+=pq.top();pq.pop();
pq.push(total);
sum+=total;
}
cout<<sum;
return 0;
}0扫雷 - 蓝桥云课 (lanqiao.cn)
#include <bits/stdc++.h>
using namespace std;
const int N=1001;
int main(){
int n,m;cin>>n>>m;
int a[N][N]={0},b[N][N]={0};//不能直接a[n][m]会导致错误应该开大一点
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
cin>>a[i][j];
}
}
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
if(a[i][j]==1){b[i][j]=9;cout<<b[i][j]<<" \n"[j==m-1];continue;}
//是地雷的话直接就输出了
for(int l=max(0,i-1);l<min(n,i+2);l++){//遍历九宫格
for(int h=max(0,j-1);h<min(m,j+2);h++){
if(a[l][h]==1)b[i][j]++;//如果附近有地雷就++
}
}
cout<<b[i][j]<<" \n"[j==m-1];
}
}
return 0;
}0灌溉 - 蓝桥云课 (lanqiao.cn)
#include <bits/stdc++.h>
using namespace std;
const int N=1000;
int main(){
int n,m;cin>>n>>m;
int a[n+1][m+1]={0},b[n+1][m+1];//b数组是答案数组
int t;cin>>t;
while(t--){int r,c;cin>>r>>c;a[r][c]=1;b[r][c]=1;}
int k;cin>>k;
while(k--){
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(a[i][j]==1){
b[i-1][j]=b[i+1][j]=b[i][j+1]=b[i][j-1]=1;
//就算溢出来也没事 因为下面遍历时候没有算上
}
}
}
//不能一遍灌溉一遍更新 不然新更新的位置会在下次继续灌溉
//时间上会乱掉
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
a[i][j]=b[i][j];//更新原来的数组
}
}
}
int cnt=0;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(b[i][j]==1)cnt++;
}
}
cout<<cnt;
return 0;
}5.数的计算 - 蓝桥云课 (lanqiao.cn)
#include <bits/stdc++.h>
using namespace std;
const int N=20;
int a[N];
int ans=1;
void dfs(int dep){//表示搜索dep层
for(int i=1;i<=a[dep-1]/2;i++){
ans++;
a[dep]=i;//每次都会更新
dfs(dep+1);
// a[dep]=0;//回溯
}
}
int main(){
int n;cin>>n;
a[1]=n;
dfs(2);
cout<<ans;//从第二层开始搜索
return 0;
}6.数的划分 - 蓝桥云课 (lanqiao.cn)
#include <iostream>
using namespace std;
int resolve(int n, int k) {//将n分为k份的所有分法
if (n < k) return 0;
if (n == k || k == 1) return 1;
return resolve(n - 1, k - 1) + resolve(n - k, k);
}//分成1.至少有一个位置是1 2.每个位置都大于1
int main() {ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int n, k; cin >> n >> k;
cout << resolve(n, k) << '\n';
return 0;
}
#include <iostream>
using namespace std;
const int N = 210, M = 10;
int f[N][M];
int main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int n, k; cin >> n >> k;
f[0][0] = 1;
for (int i = 1; i <= n; i ++) f[i][1] = 1;
for (int i = 1; i <= n; i ++)
for (int j = 2; j <= min(i, k); j ++)/最多分为min(i,k)份
f[i][j] = f[i - 1][j - 1] + f[i - j][j];
cout << f[n][k] << '\n';
return 0;
}7.涂色 - 蓝桥云课 (lanqiao.cn)
#include <bits/stdc++.h>
using namespace std;
char a[55];
int dp[55][55];
int main(){
string s;cin>>s;
s="#"+s;
int n=(int)s.size()-1;
memset(dp,0x3f3f3f,sizeof(dp));
for(int i=1;i<=n;i++)dp[i][i]=1;
for(int len=2;len<=n;len++){
for(int i=1;i+len-1<=n;i++){//右端点合法
int j=i+len-1;
if(s[i]==s[j]){
dp[i][j]=min(dp[i][j-1],dp[i+1][j]);
}else
for(int k=i;k<j;k++){//枚举所有的分割点
dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]);
}
}
}
cout<<dp[1][n];
return 0;
}
