A. There Are Two Types Of Burgers
水题。题意：给你面包片数，两种不同的肉饼数（制作一个汉堡要消耗两片面包和一片肉饼），之后再给你两种不同的汉堡售价，问你如何取得最大收益。
思路：照题意模拟即可 ，简单贪心。
#include <iostream> #include <sstream> #include <cstring> #include <string> #include <cstdio> #include <cstdlib> #include <vector> using namespace std; int main() { int t; scanf("%d", &t); while (t--) { int b, p, f; int h, c; cin >> b >> p >> f; cin >> h >> c; if (h > c) { int sum = 0; while (b >= 2 && p) sum += h, b -= 2, p--; while (b >= 2 && f) sum += c, b -= 2, f--; cout << sum << endl; } else { int sum = 0; while (b >= 2 && f) sum += c, b -= 2, f--; while (b >= 2 && p) sum += h, b -= 2, p--; cout << sum << endl; } } }
B. Square Filling
算是水题吧。但是当时我想不出来（我还是太菜了wwww），还去问了子巨（子巨tql）。
暴力枚举判断即可。
题意：你有一个0矩阵。问你是否能经过操作变成题目给你的矩阵。
思路：枚举矩阵的每一个点。之后依次turn(将周围变成1)，之后check是否与给出矩阵相符。若不符则turn_back，符合则压入vector。
注意的是可能存在都为0的情况，所以在最开始读入矩阵时，要加入flag判断是否题目给出的是0矩阵。
#include <iostream> #include <sstream> #include <cstring> #include <string> #include <cstdio> #include <cstdlib> #include <vector> using namespace std; int n, m; int cnt; int sample[51][51]; int temp[51][51]; int tmp[2][2]; vector <int> ans; int final_check(){ for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) if (temp[i][j] != sample[i][j]) return 1; return 0; } void turn_back(int x, int y){ for (int i = x; i <= x + 1; i++) for (int j = y; j <= y + 1; j++) temp[i][j] = tmp[i-x][j-y]; } void turn(int x, int y){ for (int i = 0; i <= 1; i++) for (int j = 0; j <= 1; j++) tmp[i][j] = temp[x+i][y+j]; for (int i = x; i <= x + 1; i++){ for (int j = y; j <= y + 1; j++){ temp[i][j] = 1; if (temp[i][j] != sample[i][j]){ turn_back(x, y); return ; } } } cnt++; ans.push_back(x); ans.push_back(y); } int main() { cin >> n >> m; int flag = 0; //判断是否为0矩阵 for (int i = 0; i < n; i++) for (int j = 0; j < m; j++){ scanf("%d", &sample[i][j]); if (sample[i][j]) flag = 1; } for (int i = 0; i < n-1; i++) for (int j = 0; j < m-1; j++) turn(i, j); if (!flag) cout << "0" << endl; else if (!cnt || final_check()) cout << "-1" << endl; else{ cout << cnt << endl; for (int i = 0; i < ans.size(); i+=2) cout << ans[i]+1 << " " << ans[i+1]+1 << endl; } return 0; }
C. Gas Pipeline（补题）
题意：二进制01串。为1代表这个地方得是高度为2的柱子，为0代表可以为高度为1或者2的柱子。
起点和终点柱子高度都为1。同时横向走的时候需要管道。柱子的单位花费是b，管道的单位花费是a。问怎么安排使得花费最小
思路：这道题有两种思路贪心与DP。
dp：读题不难发现，对于每个地方，要么是低位，要么是高位，影响因素只有花费和1的位置。
易得dp转移方程为 1.dp[i][0]=min(dp[i-1][1]+2*a+b,dp[i-1][0]+a+b);
2.dp[i][1]=min(dp[i-1][1]+a+2*b,dp[i-1][0]+2*a+2*b);
DP的代码：
#include <cstring> #include <algorithm> #include <cstdio> typedef long long ll; using namespace std; #define maxn 200000 + 100 char s[maxn]; ll dp[maxn][2]; int main() { ll n, a, b, t; scanf("%lld", &t); while (t--){ scanf("%lld %lld %lld %s", &n, &a, &b, s); memset(dp, 0x3f, sizeof(dp)); dp[0][0] = b; //一开始必然是低位 for (ll i = 1; i <= n; i++){ if ((s[i] == '0' && s[i-1] == '0') || i == n) dp[i][0] = min(dp[i-1][1] + 2 * a + b, dp[i-1][0] + a + b); dp[i][1] = min(dp[i-1][1] + a + 2 * b, dp[i-1][0] + 2 * a + 2 * b); } printf("%lld\n", dp[n][0]); } }
贪心：如果有n个点的话，就会有n+1个柱子。字符串为1的话，1这个格子代表的两个点都必须是是高柱子。
首先确定基础花费：n个管道：n*a，n+1个低柱子：n*b，2个转折管道：2*a。中间可以高柱子的部分，假设长度为x，选择高柱子，额外花费为x*b。选择低柱子，花费为2*a。选择最小的就可以了。
贪心代码：
#include <cstdio> #include <algorithm> #include <iostream> #include <cstring> #define maxn 200000 + 10 #define inf 0x3f3f3f3f using namespace std; typedef long long ll; ll rec_pilar[maxn]; char s[maxn]; int main(){ ll t; scanf("%lld", &t); while (t--){ memset(rec_pilar, 0, sizeof(rec_pilar)); ll n, a, b; scanf("%lld %lld %lld", &n, &a, &b); scanf("%s", s); //st和ed是用来记录高位的最左边和最右边 ll st = inf, ed = 0; for (ll i = 0; i < n; i++){ //若s为1的话那么1左右两边的柱子都应该是高位 if (s[i] == '1'){ rec_pilar[i] = 1; rec_pilar[i+1] = 1; st = min(st, i); ed = max(ed, i + 1); } } ll num0 = 0,num1 = 0; //num0记录低位，num1记录高位 ll ans = 0; for (ll i = st; i <= ed; i++){ ll tmp = 0; if (rec_pilar[i] == 0) num0++; else{ num1++; //每次加上贪心结果 ans += min(num0 * b, 2 * a); num0 = 0; } } ans += 2 * a + n * a + (n + 1) * b + num1 * b; //要是一直都是低位 if (st == inf && ed == 0) ans -= 2 * a; printf("%lld\n", ans); } return 0; }
D. Number Of Permutations（补题）
题意：给出n组二元组(x,y)。求多少种排列，使得x不递增（包括相等），y不递增（包括相等）。
思路：反向求good array，那就在总方案数 n! 中把bad array全部减掉
我们先把数组按照a排序，那么因为第一维是不降的方案就可以计算出来了，就是对于相同的一段a，他们内部可以随便交换位置，那么这段长度为len的相同的a就可以贡献 len! ,把所有len！乘起来就是 第一维不降的方案cnt1
同理按照b排序，求出第二维不降的总方案数cnt2。
之后会发现如果在a中有相同段的同时b中的相同段也有的话，就会有重复。所以之后再通过上面一样的方式乘出cnt3。如果不满足，那么说明没有重复方案，cnt3 = 0
最后答案就是 n!-cnt1-cnt2+cnt3
参考博客：
https://blog.csdn.net/liufengwei1/article/details/100030671
https://www.cnblogs.com/guangheli/p/11399824.html
#include <cstdio> #include <iostream> #include <cstring> #include <algorithm> #define maxn 300000 + 100 typedef long long ll; const int mod = 998244353; using namespace std; ll c[maxn]; int n; struct node { int a, b; }a[maxn]; bool cmp1(node a, node b) { if (a.a == b.a) return a.b < b.b; return a.a < b.a; } bool cmp2(node a, node b) { if (a.b == b.b) return a.a < b.a; return a.b < b.b; } int main() { scanf("%d", &n); ll cnt1, cnt2, cnt3; int j, i; cnt1 = cnt2 = cnt3 = c[0] = 1; for(int i = 1; i < maxn; i++) c[i] = 1ll * c[i-1] * i % mod; for(int i=0;i<n;++i) scanf("%d %d",&a[i].a,&a[i].b); sort(a,a+n, cmp1); for(i=0;i<n;i=j) { for(j=i;j<n&&a[j].a==a[i].a;++j); cnt1=cnt1*c[j-i]%mod; } sort(a,a+n,cmp2); for(i=0;i<n;i=j) { for(j=i;j<n&&a[j].b==a[i].b;++j); cnt2=cnt2*c[j-i]%mod; } int flag=0; for(i=1;i<n;++i) if(a[i].a<a[i-1].a) flag=1; if(flag) printf("%lld\n",(c[n]-(cnt1+cnt2)%mod+mod)%mod); else { for(i=0;i<n;i=j) { for(j=i;j<n&&a[j].a==a[i].a&&a[j].b==a[i].b;++j); cnt3=cnt3*c[j-i]%mod; } printf("%lld\n",(c[n]-(cnt1+cnt2-cnt3+mod)%mod+mod)%mod); } return 0; }