21山东省赛DGH

Dyson Box模拟

Grade Point Average除法模拟

Adventurer's Guild简单dp

D	Dyson Box模拟

In the only example, the inside of the box is as below, and the bold lines mark the outline of all the cubes.

After the 111-st event:

After the 222-nd event:

After the 333-rd event:

After the 444-th event:

题意:每次在矩阵内某处产生一个箱子,每个箱子会受到水平力或竖直力作用,输出每种力情况下当前箱子露出的边数.

思路:模拟一下,竖直和水平的情况分开讨论.每次产生一个箱子,先让当前的总边长加4.然后模拟各种会使露出边长减小的情况,比如叠在某个箱子上,或者紧贴着某些箱子.

#include <iostream>
#include<ctime>
#include<math.h>
#include<string>
#include<vector>
#include<queue>
#include<map>
#include<set>
#include<cstring>
#include<algorithm>
#include<limits.h>
#include<unordered_map>
#include<unordered_set>
#define ll long long
using namespace std;
const int N = 2e5 + 10;
struct node {int x, y;
}per[N];
int m1[N] = { 0 }, m2[N] = { 0 };
int main()
{ios::sync_with_stdio(false); cout.tie(NULL);int n;cin >> n;int sum1 = 0, sum2 = 0;for (int j = 1; j <= n; j++) {sum1 += 4; sum2+= 4;int t1, t2;cin >> per[j].x >> per[j].y;t1 = per[j].x; t2 = per[j].y;if (m1[t1])sum1 -= 2;if (m1[t1] + 1 <= m1[t1 - 1] )sum1 -= 2;if (m1[t1] + 1 <= m1[t1 + 1])sum1 -= 2;if (m2[t2])sum2 -= 2;if (m2[t2] + 1 <= m2[t2 + 1])sum2 -= 2;if (((m2[t2] + 1) <= m2[t2 - 1]))sum2 -= 2;m1[per[j].x]++; m2[per[j].y]++;//记录箱子摆放情况cout << sum1 << " " << sum2 << endl;}
}

G	Grade Point Average除法模拟

题意:对一段数列求取平均数,小数点后保留k位,不四舍五入.

思路:除法模拟.

#include<iostream>
#include<vector>
#include<string>
using namespace std;
void div(long long s,int n,int k){vector<int>c;string ans=to_string(s/n)+".";//先取出整数部分s%=n;while(k--){//开始模拟小数点后的除法int t=(s*10)/n;//除完得到的数ans+=to_string(t);s=(s*10)%n;//除完剩下的数}cout<<ans<<endl;
}
int main(){
//freopen("in.txt", "r", stdin);
//freopen("out.txt", "w", stdout);int n,k;cin>>n>>k;long long  sum=0;for(int j=1;j<=n;j++){int t;cin>>t;sum+=t;}div(sum,n,k);
}

H	Adventurer's Guild简单dp

题意:其实就是冒险者有生命值和耐力值两种限制,打完每个怪物会扣除对应的生命值和耐力值.但会得到对应的价值. 生命值<=0则死亡,耐力值小于0的部分会由生命值承担. 目前有n个怪物,求你能得到的最大价值.

思路:其实是一道很明显的01背包问题,但是多了个耐力值的限制,不过也很好讨论耐力值小于0的情况转移到耐力值为0生命值而外减去对应的溢出耐力值即可.

状态转移方程:

 dp[j][i][k] = dp[j - 1][i][k]; 
if (k < per[j].s) {if (i - per[j].h - (per[j].s - k) > 0) dp[j][i][k] = max(dp[j - 1][i][k], dp[j - 1][i - per[j].h - (per[j].s - k)][0] + per[j].w);else dp[j][i][k] = max(dp[j - 1][i][k], dp[j - 1][i - per[j].h][k - per[j].s] +per[j].w);

数据1000*300*300看起来好像能撑的过去

如果直接三维暴力话

#include <iostream>
#include<ctime>
#include<math.h>
#include<string>
#include<vector>
#include<queue>
#include<map>
#include<set>
#include<cstring>
#include<algorithm>
#include<limits.h>
#include<unordered_map>
#include<unordered_set>
#define ll long long
using namespace std;
const int N = 1e3 + 10;
ll n, hh, ss;
struct node {int h, s, w;
}per[N];
int  dp[1010][310][310] ;
int main()
{ios::sync_with_stdio(false); cout.tie(NULL);cin >> n >> hh >> ss;for (int j = 1; j <= n; j++) {ll h, s, w;cin >> h >> s >> w;per[j].h = h, per[j].s = s, per[j].w = w;}for (int j = 1; j <= n; j++) {for (int i = 1; i <= hh; i++) {for (int k = 0; k <= ss; k++) {dp[j][i][k] = dp[j - 1][i][k];//注意这里如果没有成功转移则继承上一个状态if (i > per[j].h) {if (k < per[j].s) {if (i - per[j].h - (per[j].s - k) > 0) {dp[j][i][k] = max(dp[j - 1][i][k], dp[j - 1][i - per[j].h - (per[j].s - k)][0] + per[j].w);}}else {dp[j][i][k] = max(dp[j - 1][i][k], dp[j - 1][i - per[j].h][k - per[j].s] + per[j].w);}}}}}cout << dp[n][hh][ss];
}

还是爆内存了,于是乎想到01背包的二维优化.

#include <iostream>
#include<ctime>
#include<math.h>
#include<string>
#include<vector>
#include<queue>
#include<map>
#include<set>
#include<cstring>
#include<algorithm>
#include<limits.h>
#include<unordered_map>
#include<unordered_set>
#define ll long long
using namespace std;
const int N = 1e3 + 10;
ll n, hh, ss;
struct node {ll h, s, w;
}per[N];
ll dp[310][310]={0};
int main()
{ios::sync_with_stdio(false); cout.tie(NULL);cin >> n >> hh >> ss;for (int j = 1; j <= n; j++) {ll h, s, w;cin >> h >> s >> w;per[j].h = h, per[j].s = s, per[j].w=w;}for (int j = 1; j <= n; j++) {for (int i = hh; i >per[j].h; i--) {for (int k = ss; k >=0; k--) {if (k - per[j].s < 0) {if (i - per[j].h - (per[j].s - k) > 0)dp[i][k] = max(dp[i - per[j].h - (per[j].s - k)][0] + per[j].w, dp[i][k]);}else {dp[i][k] = max(dp[i - per[j].h][k - per[j].s] + per[j].w, dp[i][k]);}}}}cout << (dp[hh][ss]) << endl;
}