今天本来打算把剩下两种背包刷完的...然后被队友拖去打比赛，这还算相对友好一些吧，还剩下几题我不会做。明天有空补上。
【2019-7-17填坑】 G
比赛地址：https://ac.nowcoder.com/acm/contest/993#question
【A】 Card Stacking
n 个人玩 k 张牌，发牌员是 n 号，一共有 k/n 张好牌，发牌员全都要，问需要把好牌放在哪里才能拿到。（发牌规则：从 1 号开始，每次发一张牌，发完之后把牌堆顶部的 p 张牌全部放到牌堆底部。然后继续发牌。）
很基础的模拟题，就因为想的太简单了，WA了1发（queue爆了）。后面数组模拟队列就过了。
#include <map>
#include <set>
#include <list>
#include <cmath>
#include <ctime>
#include <deque>
#include <stack>
#include <queue>
#include <bitset>
#include <cctype>
#include <cstdio>
#include <vector>
#include <string>
#include <cstdlib>
#include <cstring>
#include <fstream>
#include <iomanip>
#include <numeric>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const double PI = acos(-1.0);
const double eps = 1e-6;
const int inf = 0x3f3f3f3f;
const int mod = 1e9 + 7;
queue<int> q;
vector<int> v[105];
int main() {
int n, k, p;
while(~scanf("%d%d%d", &n, &k, &p)) {
for(int i = 0; i <= 100; i++) {
v[i].clear();
}
for(int i = 1; i <= k; i++) {
q.push(i);
}
int x = 1;
while(!q.empty()) {
int f = q.front();
q.pop();
v[x].push_back(f);
for(int i = 1; i <= p; i++) {
int ff = q.front();
q.pop();
q.push(ff);
}
x++;
if(x > n) {
x = 1;
}
}
sort(v[n].begin(), v[n].end());
int s = k/n;
for(int i = 0; i < s; i++) {
printf("%d
", v[n][i]);
}
}
return 0;
}
【B】 Bookshelf
n个物体，给定高度，问最少选择多少个可以使高度超过 m。
就...水题。
#include <map>
#include <set>
#include <list>
#include <cmath>
#include <ctime>
#include <deque>
#include <stack>
#include <queue>
#include <bitset>
#include <cctype>
#include <cstdio>
#include <vector>
#include <string>
#include <cstdlib>
#include <cstring>
#include <fstream>
#include <iomanip>
#include <numeric>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const double PI = acos(-1.0);
const double eps = 1e-6;
const int inf = 0x3f3f3f3f;
const int mod = 1e9 + 7;
const int maxn = 2e4+5;
int a[maxn];
int main() {
int n;
ll m;
while(~scanf("%d%lld", &n, &m)) {
for(int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
}
ll sum = 0;
int cnt = 0;
sort(a+1, a+1+n);
for(int i = n; i >= 1; i--) {
sum = sum + a[i];
cnt ++;
if(sum >= m) {
break;
}
}
printf("%d
", cnt);
}
return 0;
}
【C】 Bookshelf 2
在 B 题的基础上，问在超过的给定高度的情况下，最小的多余值是多少。
队友做的，dfs 搜索一下，对于每个数来说分为取或者不取，然后再判断最小就行了。
#include <map>
#include <set>
#include <list>
#include <cmath>
#include <ctime>
#include <deque>
#include <stack>
#include <queue>
#include <bitset>
#include <cctype>
#include <cstdio>
#include <vector>
#include <string>
#include <cstdlib>
#include <cstring>
#include <fstream>
#include <iomanip>
#include <numeric>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const double PI = acos(-1.0);
const double eps = 1e-6;
const int inf = 0x3f3f3f3f;
const int mod = 1e9 + 7;
const int maxn = 1e5+5;
int a[maxn], ans, n, m;
void dfs(int d, int num){
if(d == n+1){
if(num >= m){
ans = min(ans, num - m);
}
return ;
}
if(ans == 0)
return;
dfs(d+1, num);
dfs(d+1, num+a[d]);
}
int main(){
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; i++)
scanf("%d", &a[i]);
ans = int(1e9);
dfs(1, 0);
printf("%d", ans);
return 0;
}
【D】 迷路的牛
还是队友做的。题意我都没看...
#include <map>
#include <set>
#include <list>
#include <cmath>
#include <ctime>
#include <deque>
#include <stack>
#include <queue>
#include <bitset>
#include <cctype>
#include <cstdio>
#include <vector>
#include <string>
#include <cstdlib>
#include <cstring>
#include <fstream>
#include <iomanip>
#include <numeric>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const double PI = acos(-1.0);
const double eps = 1e-6;
const int inf = 0x3f3f3f3f;
const int mod = 1e9 + 7;
int main(){
int a[4];
for(int i = 1; i <= 3; i++) {
scanf("%d", &a[i]);
}
sort(a+1, a+1+3);
int minl = inf;
int maxl = 0;
for(int i = 2; i <= 3; i++) {
minl = min(minl, a[i]-a[i-1]);
maxl = max(maxl, a[i]-a[i-1]);
}
minl--;
maxl--;
if(minl == 0) {
minl = maxl;
}
if(minl >= 2) {
minl = 2;
}
else if(minl == 1) {
minl = 1;
}
printf("%d
%d
",minl,maxl);
return 0;
}
【E】 对牛排序
给定 n 头牛，和每个人的编号，每次只能操作第一只牛，问几步能还原顺序。
没啥好说的，就是算序列从后往前有几个连续降序。
#include <map>
#include <set>
#include <list>
#include <cmath>
#include <ctime>
#include <deque>
#include <stack>
#include <queue>
#include <bitset>
#include <cctype>
#include <cstdio>
#include <vector>
#include <string>
#include <cstdlib>
#include <cstring>
#include <fstream>
#include <iomanip>
#include <numeric>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const double PI = acos(-1.0);
const double eps = 1e-6;
const int inf = 0x3f3f3f3f;
const int mod = 1e9 + 7;
const int maxn = 1e3+5;
int a[maxn];
int main() {
int n;
while(~scanf("%d", &n)) {
for(int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
}
int temp = 1;
for(int i = n; i > 1; i--) {
if(a[i] > a[i-1]) {
temp++;
}
else {
break;
}
}
printf("%d
", n-temp);
}
return 0;
}
【F】 Mud Puddles
还是队友做的。没看题...
#include<iostream>
#include<algorithm>
#include<stdio.h>
#include<string.h>
#include<set>
#include<queue>
#include<math.h>
using namespace std;
typedef long long int ll;
#define lson rt<<1
#define rson rt<<1|1
const ll mod=1e9+7;
const ll maxn=4000;
const int inf=0x7fffffff;
struct node{
int x,y,step;
};
int map[1056][1056];
int dir[4][2]={1,0,0,1,-1,0,0,-1};
bool vis[1056][1056];
int bfs()
{
queue<node> q;
node a;
a.step=0;
a.x=500;
a.y=500;
q.push(a);
while(!q.empty())
{
node t=q.front();
q.pop();
if(map[t.x][t.y]==1)
return t.step;
for(int i=0;i<4;i++)
{
int tx=t.x+dir[i][0];
int ty=t.y+dir[i][1];
if(tx<0||ty<0||tx>1000||ty>1000||vis[tx][ty]||map[tx][ty]==-1)
{
continue;
}
node k;
k.x=tx;
k.y=ty;
k.step=t.step+1;
q.push(k);
vis[tx][ty]=1;
}
}
}
int main(){
int x,y,n;
cin>>x>>y>>n;
memset(map,0,sizeof(map));
memset(vis,0,sizeof(vis));
map[x+500][y+500]=1;
for(int i=1;i<=n;i++)
{
int a,b;
cin>>a>>b;
map[a+500][b+500]=-1;
}
int ans=bfs();
printf("%d
",ans);
return 0;
}
【G】 Cow Yahtzee
待填坑...没猜错的话应该是大模拟，然后我没想明白怎么枚举才能不重复就是了。
【我真是...这数据确定不是用 jio 造的吗。为什么复杂度 (8^{20}) 都能过... 】
#include <map>
#include <set>
#include <list>
#include <cmath>
#include <ctime>
#include <deque>
#include <stack>
#include <queue>
#include <bitset>
#include <cctype>
#include <cstdio>
#include <vector>
#include <string>
#include <cstdlib>
#include <cstring>
#include <fstream>
#include <iomanip>
#include <numeric>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const double PI = acos(-1.0);
const double eps = 1e-6;
const int inf = 0x3f3f3f3f;
const int mod = 1e9 + 7;
struct node {
int count, number;
};
vector<node> v[25];
int n, s, e;
int vis[25];
int ans;
void dfs(int x) {
if(x == n) { // 凑满 n 个开始判断
for(int i = 1; i <= e; i++) {
int f = 1;
for(int j = 0; j < v[i].size(); j++) {
if(v[i][j].count > vis[v[i][j].number]) {
f = 0;
break;
}
}
if(f == 1) {
ans ++;
return ;
}
}
return ;
}
for(int i = 1; i <= s; i++) { // 枚举所有面
vis[i] ++;
dfs(x+1);
vis[i] --;
}
}
int main() {
while(~scanf("%d%d%d", &n, &s, &e)) {
for(int i = 0; i < 25; i++) {
v[i].clear();
}
memset(vis, 0, sizeof(vis));
ans = 0;
for(int i = 1; i <= e; i++) {
char ch;
int c, n;
do {
scanf("%d%*c%d%c", &c, &n, &ch);
v[i].push_back({c, n});
}while(ch != '
');
}
dfs(0);
printf("%d
", ans);
}
return 0;
}
【H】 Charm Bracelet
01背包裸题...昨天练的居然派上用场了...xswl。
#include <map>
#include <set>
#include <list>
#include <cmath>
#include <ctime>
#include <deque>
#include <stack>
#include <queue>
#include <bitset>
#include <cctype>
#include <cstdio>
#include <vector>
#include <string>
#include <cstdlib>
#include <cstring>
#include <fstream>
#include <iomanip>
#include <numeric>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const double PI = acos(-1.0);
const double eps = 1e-6;
const int inf = 0x3f3f3f3f;
const int mod = 1e9 + 7;
const int maxn = 2e4+5;
int dp[maxn];
int a[maxn], b[maxn];
int main() {
int n, m;
while(~scanf("%d%d", &n, &m)) {
for(int i = 1; i <= n; i++) {
scanf("%d%d", &a[i], &b[i]);
}
memset(dp, 0, sizeof(dp));
for(int i = 1; i <= n; i++) {
for(int j = m; j >= a[i]; j--) {
dp[j] = max(dp[j], dp[j-a[i]]+b[i]);
}
}
printf("%d
", dp[m]);
}
return 0;
}
【I】 新游戏
待填坑...看旁边的朋友改了一下午bug...明天也尝试一下好了。
【J】 Sightseeing Cows
待填坑...这题感觉很难啊...为何通过率如此之高。
【K】 Gourmet Grazers
有 n 头牛， m 种草，每头牛对于草的需求是两项指标都要满足，问最少要花多少钱才能满足所有牛。
multiset 的思维题，想排序方法我想了一中午...
#include <map>
#include <set>
#include <list>
#include <cmath>
#include <ctime>
#include <deque>
#include <stack>
#include <queue>
#include <bitset>
#include <cctype>
#include <cstdio>
#include <vector>
#include <string>
#include <cstdlib>
#include <cstring>
#include <fstream>
#include <iomanip>
#include <numeric>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const double PI = acos(-1.0);
const double eps = 1e-6;
const int inf = 0x3f3f3f3f;
const int mod = 1e9 + 7;
const int maxn = 1e5+5;
struct node{
int p, s;
bool operator < (const node &a) const {
if(s == a.s)
return p < a.p;
return s > a.s;
}
}cow[maxn], grass[maxn];
int main() {
int n, m;
multiset<int> ms;
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; i++) {
scanf("%d%d", &cow[i].p, &cow[i].s);
}
for(int i = 1; i <= m; i++) {
scanf("%d%d", &grass[i].p, &grass[i].s);
}
sort(cow+1, cow+1+n);
sort(grass+1, grass+1+m);
int flag = 1;
ll ans = 0;
int cnt = 0;
for(int i = 1; i <= n; i++) {
while(flag <= m) {
if(grass[flag].s >= cow[i].s) {
ms.insert(grass[flag].p);
flag ++;
}
else {
break;
}
}
auto it = ms.lower_bound(cow[i].p);
if(it == ms.end()) {
cnt = -1;
break;
}
else {
ans += (*it);
ms.erase(it);
}
}
if(cnt == -1) {
printf("-1
");
}
else {
printf("%lld
", ans);
}
return 0;
}
【L】 Best Cow Line
给定字符串，每次只能从头或者尾取一个字符，问最小的字典序排列是什么。
HASH 题，后缀数组也可做，没看到题目要求的 80 个字符串换行...三个人debug了好久...多亏了隔壁的热心大佬。
#include <map>
#include <set>
#include <list>
#include <cmath>
#include <ctime>
#include <deque>
#include <stack>
#include <queue>
#include <bitset>
#include <cctype>
#include <cstdio>
#include <vector>
#include <string>
#include <cstdlib>
#include <cstring>
#include <fstream>
#include <iomanip>
#include <numeric>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const double PI = acos(-1.0);
const double eps = 1e-6;
const int inf = 0x3f3f3f3f;
const int mod = 1e9 + 7;
const int maxn = 5e5+5;
char a[maxn], b[maxn], c[maxn];
ull ahash[maxn], bhash[maxn], f[maxn];
int n;
const ull seed = 13331;
ull get_a(int l, int r){
return ahash[r] - ahash[l-1]*f[r-l+1];
}
ull get_b(int l, int r){
return bhash[r] - bhash[l-1]*f[r-l+1];
}
void init(){
ahash[0] = a[0]-'A';
for(int i = 1; i < n; i++){
ahash[i] = ahash[i-1]*seed + a[i] - 'A';
}
bhash[0] = b[0]-'A';
for(int i = 1; i < n; i++){
bhash[i] = bhash[i-1]*seed + b[i] - 'A';
}
f[0] = 1;
for(int i = 1; i <= n; i++){
f[i] = f[i-1]*seed;
}
}
int solve(int ba, int bb){
int len = n - ba - bb ;
int l = 1, r = len, ans = 0;
while(l < r){
int m = (l+r)>>1;
if(get_a(ba, ba+m-1) == get_b(bb, bb+m-1)){
ans = m;
l = m+1;
}
else
r = m;
}
if(ans == len){
return 1;
}
else{
if(a[ba+ans] > b[bb+ans])
return 0;
else
return 1;
}
}
int main(){
char x[15];
int cnt = 0;
scanf("%d", &n);
for(int i = 0; i < n; i++){
scanf("%s", x);
a[i] = x[0];
}
a[n] = ' ';
strcpy(b, a);
reverse(b, b+n);
init();
int i = 0, j = 0;
while(i + j < n){
if(a[i] < b[j]){
c[i+j] = a[i];
i++;
}
else if(a[i] > b[j]){
c[i+j] = b[j];
j++;
}
else{
if(solve(i, j) == 1){
c[i+j] = a[i];
i++;
}
else{
c[i+j] = b[j];
j++;
}
}
}
for(int i = 0; i < n; i++) {
printf("%c", c[i]);
cnt ++;
if(cnt == 80) {
cnt = 0;
printf("
");
}
}
return 0;
}
相信我，我一定会补题的【咕咕咕】。