蓝桥杯练习1163-1176

1176：遍历

遍历
题意：
给定N个点的图，求经过指定M个点的路径，使路径最短
思路：
状压dp。
//无语住了。。。。找了好久bug以为是思路问题，最后发现是没有弄清楚M个点里面可以重复的。。

#include<bits/stdc++.h> 
#define all(x) x.begin(),x.end()
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define pll pair<ll,ll>
using namespace std;
typedef long long ll;const double eps=1e-8;
const double PI=acos(-1.0);
const ll mod = 1e9+7;
const ll mx = 1e2 + 10;
const ll mx2 = 4e4 + 10;
const ll inf = 1<<30;ll N, M, d[mx][mx], dis[mx][mx];
ll id[mx];
bool b[mx];
ll dp[mx][mx2];
// 1<<15 == 32768void solve(){
    scanf("%lld %lld", &N, &M);for(ll i = 1; i <= N; i++){
    for(ll j = 1; j <= N; j++){
    scanf("%lld", &d[i][j]);if(d[i][j] == 0 && i!=j)d[i][j] = inf;}}ll cM = 1;for (ll i = 1; i <= M; i++) {
    scanf("%lld", &id[cM]);id[cM]++;if (b[id[cM]])continue;b[id[cM]] = true;cM++;}M = cM - 1;for(ll k = 1; k <= N; k++)for(ll i = 1; i <= N; i++)for(ll j = 1; j <= N; j++)d[i][j] = min(d[i][j],d[i][k]+d[k][j]);for(ll i = 1; i <= M; i++)for(ll j = 1; j <= M; j++)dis[i][j] = d[id[i]][id[j]];	for(ll i = 1; i <= M; i++)for(ll j = 0; j <= (1<<M)-1; j++)dp[i][j] = inf;for(ll i = 1; i <= M; i++)dp[i][0] = 0;		 for(ll i = 1; i < (1<<M); i++){
    for(ll j = 1; j <= M; j++){
    if((i>>(j-1))&1)continue;// j - 0//dp[j][i]for(ll k = 1; k <= M; k++){
    if(!((i>>(k-1))&1))continue;//k - 1dp[j][i] = min(dp[j][i], dis[j][k]+dp[k][i-(1<<(k-1))]);}}}ll ans = inf;for(ll i = 1; i <= M; i++){
    ll cv = (1<<M) - 1 - (1<<(i-1));ans = min(ans, dp[i][cv]);}printf("%lld\n", ans==inf?-1:ans);}int main(){
    solve();return 0;
}

1175：打包

打包
题意：
N个礼物分为M份包裹，每份包裹的礼物的号都是连续的。求最小的（最大一份包裹的重量）。
思路：
二分答案。二分值为w，则从第一个礼物开始贪心地取当前份的包裹里的礼物直到重量超标，超标了就新建一份包裹，如果即使新建也装不下则当前w不合适。如果最后包裹数量超过M也不合适。

#include<bits/stdc++.h> 
#define all(x) x.begin(),x.end()
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define pll pair<ll,ll>
using namespace std;
typedef long long ll;const double eps=1e-8;
const double PI=acos(-1.0);
const ll mod = 1e9+7;
const ll mx = 1e5 + 10;
ll N, M, d[mx];bool check(ll w){
    ll c = 0, m = 1; for(ll i = 1; i <= N; i++){
    c += d[i];if(c > w){
    m++;c = d[i];if(c > w) return false;}} return m <= M;
}void solve(){
    scanf("%lld %lld", &N, &M);for(ll i = 1; i <= N;i ++) scanf("%lld", &d[i]);ll small = 0, big = 1000*100000;while(small <= big){
    ll mid = (small + big) >>1;if(check(mid)) big = mid-1LL;else small = mid+1LL;}printf("%lld\n",  small);}
int main(){
    solve();return 0;
}

1174：最大连续子段和

最大连续子段和
题目：
长度为N的数列求最大连续字段和
思路：
dp。注意特判所有值都是负数的情况。

#include<bits/stdc++.h> 
#define all(x) x.begin(),x.end()
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define pll pair<ll,ll>
using namespace std;
typedef long long ll;const double eps=1e-8;
const double PI=acos(-1.0);
const ll mod = 1e9+7;
const ll mx = 1e5 + 10;
ll N, a[mx];void solve(){
    scanf("%lld", &N);for(ll i = 1; i <= N; i++) scanf("%lld", &a[i]);bool negative = true;ll maxv = -100000 * 100000;for(ll i = 1; i <= N; i++){
    if(a[i] >= 0) negative = false;maxv = max(maxv, a[i]);}if(negative){
    printf("%lld\n", maxv);return;}ll ans = -100000 * 100000;ll cans = 0;for(ll i = 1; i <= N; i++){
    cans += a[i];if(cans < 0) cans = 0;ans = max(ans, cans);}printf("%lld\n", ans); 
}int main(){
    solve();return 0;
}

1173：学生节

学生节
题意：
n个节目，T个询问。每次询问在第1个到第t[i]个节目中选择m个可以得到的最大的节目价值之和。
思路：
维护的是前t[i]个节目中最大的m个节目的价值之和。用优先队列维护m个最大值。遇到比当前优先队列里的最小值要大的v[i]的时候，就弹出这个最小值压入当前v[i]，然后更新当前维护的价值。
坑点：忘了特判0的情况，会出现运行错误，找了好久泪目。

#include<bits/stdc++.h> 
#define all(x) x.begin(),x.end()
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define pll pair<ll,ll>
using namespace std;
typedef long long ll;const double eps=1e-8;
const double PI=acos(-1.0);
const ll mod = 1e9+7;
const ll mx = 1e3 + 10;ll N, M, T;
ll v[mx], t[mx], ans[mx];
priority_queue<ll, vector<ll>, greater<ll> >q;
ll dp[mx][mx];
void solve(){
    scanf("%lld %lld %lld", &N, &M, &T);for(ll i = 1; i <= N; i++) scanf("%lld", &v[i]);for(ll i = 1; i <= T; i++) scanf("%lld", &t[i]);if(N == 0LL || M == 0LL){
    for(ll i = 1; i <= T; i++) printf("0\n");return;}for(ll i = 1; i <= N; i++){
    if(v[i]<=0){
    ans[i]=ans[i-1];continue;}if(q.size() < M){
    ans[i]=ans[i-1]+v[i];q.push(v[i]); }else{
    ll cv = q.top();if(v[i]>cv){
    q.pop();q.push(v[i]);ans[i]=ans[i-1]-cv+v[i];}else{
    ans[i]=ans[i-1];}}}for(ll i = 1; i <= T; i++){
    printf("%lld\n", ans[t[i]]);}
}int main(){
    solve();return 0;
}

1170：阶乘测试

阶乘测试 练习系统里的数据有问题 很难受
题意：略
思路：略

#include<bits/stdc++.h> 
#define all(x) x.begin(),x.end()
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define pll pair<ll,ll>
using namespace std;
typedef long long ll;const double eps=1e-8;
const double PI=acos(-1.0);
const ll mod = 1e9+7;
const ll mx = 1e3 + 10;
ll n, m;
void solve(){
    while(scanf("%lld %lld", &n, &m)!=EOF){
    ll ans = 0, base = m;while(n>=m){
    ans += n/m;m *= base;}printf("%lld\n", ans);}
}
int main(){
    solve();return 0;
}

1169：区间覆盖问题

区间覆盖问题
题意：
区间[1,n]，有m个 线段 区间。求至少需要几个区间才能覆盖区间[1,n]
思路：
贪心，对于每个区间[i,?]显然选择？最大的小区间，因此m个区间可以贪心为每个位置i对应一个小区间[i,?max]。
从位置1开始覆盖到它可以覆盖的最大值，并且这个过程中一直更新覆盖位置的？的最大值。到了位置1的可覆盖的最大值之后，下一个选择的区间的最大范围就是之前更新的记录值。如此一直更新到最后。

#include<bits/stdc++.h> 
#define all(x) x.begin(),x.end()
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define pll pair<ll,ll>
using namespace std;
typedef long long ll;const double eps=1e-8;
const double PI=acos(-1.0);
const ll mod = 1e9+7;
const ll mx = 1e6 + 10;
const ll inf = 1<<30;ll n, m, d[mx];ll norm(ll x){
    if(x <= 0) return 1;if(x > n) return n;return x;
}void solve(){
    scanf("%lld %lld", &n, &m);for(ll i = 1LL; i <= m; i++){
    ll x, y;scanf("%lld %lld", &x, &y);x = norm(x), y = norm(y);d[x]=max(d[x], y);}	ll num=0, maxv = 0, aimv=1;//最远可以覆盖的范围 bool yes= true;for(ll i = 1; i < n & yes; i++){
    maxv = max(maxv, d[i]);if(i == aimv){
    aimv = maxv;num++;}if(aimv <= i){
    yes = false;break;}}yes = yes & (maxv >= n); if(yes) printf("%lld\n", num);else printf("-1\n");
}int main(){
    solve();return 0;
}

1168：最大流

最大流
让人怀疑智商的一道题。。求两者之和

#include<bits/stdc++.h> 
using namespace std;
typedef long long ll;
ll a, b; 
int main(){
    scanf("%lld %lld", &a, &b);printf("%lld\n", a+b); return 0;
}

1164：和谐宿舍

和谐宿舍
题意：
已知n列高度，第i列的高度为h[i]。现在要求取最多m块木板从左到右排成一排并且底边在同一底线上，然后覆盖所有的高度。
求面积最大的木块的面积的 最小值。
思路：
二分答案。

#include<bits/stdc++.h> 
#define all(x) x.begin(),x.end()
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define pll pair<ll,ll>
using namespace std;
typedef long long ll;const double eps=1e-8;
const double PI=acos(-1.0);
const ll mod = 1e9+7;
const ll mx = 1e5+ 10;
const ll inf = 1<<30;ll n, m, h[mx];
bool check(ll x){
    ll currm = 0;ll ch = 0, res = 0;ll i = 1;while(i <= n){
    ch = h[i];if(ch > x) return false;res = x / ch;//可以覆盖res列 ll j = i, cres = 0; while(cres<res){
    cres++; //目前是ch高度下的第cres列 j++;if(j > n)break;if(h[j]>ch){
    //考虑抬高高度 ll nres = x/h[j];//如果抬高的最多列数 if(nres > cres){
    //可以换 res = nres;ch =  h[j];} else{
    //下一列j覆盖不到了break;}}}i = j;//覆盖不到的那一列 currm++;}return currm <= m;
}void solve(){
    scanf("%lld %lld", &n, &m);for(ll i = 1; i <= n; i++) scanf("%lld", &h[i]);ll zuo = 1, you = 100000LL * 10000LL;while(zuo <= you){
    ll mid = (zuo + you)>>1;if(check(mid)) you = mid - 1;else zuo = mid + 1;}printf("%lld\n", zuo);
}int main(){
    solve();return 0;
}

1163：网格贪吃蛇

网格贪吃蛇
题意：
m行n列，k个格子上有豆豆。蛇从(0,0)开始，每步只能往右走或者往上走，最后到达(m-1,n-1)，求可以吃的最多的豆豆数。
思路：
普通的dp。但是由于数据范围过大k过小，需要离散化先。

#include<bits/stdc++.h> 
#define all(x) x.begin(),x.end()
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define pll pair<ll,ll>
using namespace std;
typedef long long ll;const double eps=1e-8;
const double PI=acos(-1.0);
const ll mod = 1e9+7;
const ll mx = 1e3+ 10;
const ll inf = 1<<30;
ll n, m, k;
bool has[mx][mx];
ll dp[mx][mx];ll in1[mx], in2[mx];
map<ll,ll> id1, id2;
vector<ll>v1, v2;void solve(){
    scanf("%lld %lld", &m, &n);//m行数 n列数 scanf("%lld", &k);v1.pb(0), v1.pb(n-1);//x坐标 [0,n-1]v2.pb(0), v2.pb(m-1);//y坐标 [0,m-1] for(ll i = 1; i <= k; i++){
    scanf("%lld %lld", &in1[i], &in2[i]);v1.pb(in1[i]);v2.pb(in2[i]);}//离散化sort(all(v1));sort(all(v2));v1.erase(unique(all(v1)), v1.end());v2.erase(unique(all(v2)), v2.end());for(ll i = 0; i < v1.size();i ++)//x坐标 id1[v1[i]] = i+1;for(ll i = 0; i < v2.size(); i++)//y坐标 id2[v2[i]] = i+1; //数据 for(ll i = 1; i <= k; i++){
    has[id2[in2[i]]][id1[in1[i]]] = true;} m = v2.size();//行 y坐标 n = v1.size();//列 x坐标 //DP for(ll i = 1; i <= m; i++){
    //行y for(ll j = 1; j <= n; j++){
    //列x dp[i][j] = max(dp[i-1][j], dp[i][j-1]);dp[i][j] += has[i][j]?1:0; }}printf("%lld\n", dp[m][n]);
}int main(){
    solve();return 0;
}