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个数加上belse 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)/2else 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]);}elsefor(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;
}