暑假N天乐【比赛篇】 —— 2019牛客暑期多校训练营（第六场） 【A】 Garbage Classification 水题 【B】 Shorten IPv6 Address 模拟 【C】 Palindrome Mouse 回文自动机 【D】 Move 思维/二分 【E】 Androgynos 构造 【G】 Is Today Friday? 暴力 【J】 Upgrading Technology 贪心
疯狂摸鱼ing...不想写了。
以下题解包括：(A B C D E G J)
比赛地址： https://ac.nowcoder.com/acm/contest/886#question
签到题，不说了。
#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 = 2000+5;
map<char, char> mp;
char a[maxn], b[maxn];
int main() {
int t, cas = 1;
scanf("%d", &t);
while(t--) {
mp.clear();
scanf("%s%s", a, b);
for(int i = 0; i < 26; i++) {
mp[i+'a'] = b[i];
}
int n = strlen(a);
int H = 0, W = 0, D = 0;
for(int i = 0; i < n; i++) {
if(mp[a[i]] == 'h') {
H ++;
}
else if(mp[a[i]] == 'd') {
D ++;
}
else {
W ++;
}
}
printf("Case #%d: ", cas++);
if(H*4 >= n) {
printf("Harmful
");
}
else if(H*10 <= n) {
printf("Recyclable
");
}
else if(D >= 2*W){
printf("Dry
");
}
else {
printf("Wet
");
}
}
return 0;
}
【B】 Shorten IPv6 Address 模拟
给定一个长度 128 位的 01 字符串，按照规则进行变换成16进制的 (ipv6) 地址，输出变换后字典序最小的字符串。
纯大模拟，虽然 (python) 很好写，但我不会啊。代码是现场敲的，极丑将就看吧。
#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;
char s[maxn];
char str[50][50];
char str_[50][50];
struct node {
int l, r;
bool operator < (const node& a) const{
if((r-l+1) == (a.r-a.l+1)) {
return l > a.l;
}
return (r-l+1) > (a.r-a.l+1);
}
}p[50];
int main() {
int t, cas=1;
scanf("%d", &t);
while(t--) {
memset(str, ' ', sizeof(str));
memset(str_, ' ', sizeof(str_));
memset(s, ' ', sizeof(s));
int cnt = 0;
scanf("%s", s);
for(int i = 0; i < 128; i+=16) {
char temp[50];
int zzz = 0;
for(int j = i; j < i+16; j+=4) {
int sum = 0;
int x1 = s[j] - '0';
int x2 = s[j+1] - '0';
int x3 = s[j+2] - '0';
int x4 = s[j+3] - '0';
sum = sum + (x1*8 + x2*4 + x3*2 + x4);
if(sum >= 10) {
temp[zzz++] = 'a'+sum-10;
}
else {
temp[zzz++] = '0'+sum;
}
}
temp[zzz] = ' ';
strcpy(str[cnt++], temp);
}
for(int i = 0; i < cnt; i++) {
int flag = 1;
for(int j = 0; j < 4; j++) {
if(str[i][j] != '0') {
flag = 0;
}
}
// cout << flag << endl;
if(flag) { // 全 0
str_[i][0] = '0';
}
else { // 去前导 0
int j;
for(j = 0; j < 4; j++) {
if(str[i][j] != '0') {
break;
}
}
for(int k = j; k < 4; k++) {
str_[i][k-j] = str[i][k];
}
str_[i][4-j] = ' ';
}
}
int tot = 0;
int j = 0;
for(int i = 0; i < cnt; i++) {
if(strcmp(str_[i], "0") == 0) {
for(j = i+1; j < cnt; j++) {
if(strcmp(str_[j], "0") != 0) {
break;
}
}
p[tot].l = i;
p[tot++].r = j-1;
}
}
sort(p, p+tot);
p[tot].l = inf;
p[tot++].r = 0;
char ans[maxn] = {' '};
int MIN = inf;
for(int k = 0; k < tot; k++) {
char tep[maxn] = {' '};
int len = p[k].r - p[k].l + 1;
int ok = 0;
int res = 0;
if(len >= 2) {
ok = 1;
}
for(int i = 0; i < cnt; i++) {
if(ok == 0) {
int m = strlen(str_[i]);
for(int j = 0; j < m; j++) {
tep[res++] = str_[i][j];
}
if(i==cnt-1) {
tep[res++] = ' ';
}
else {
tep[res++] = ':';
}
}
else {
if(p[k].l == i) {
if(i == 0) {
tep[res++] = ':';
tep[res++] = ':';
}
else {
tep[res++] = ':';
}
i = p[k].r;
if(i == cnt-1) {
tep[res++] = ' ';
}
continue;
}
int m = strlen(str_[i]);
for(int j = 0; j < m; j++) {
tep[res++] = str_[i][j];
}
if(i==cnt-1) {
tep[res++] = ' ';
}
else {
tep[res++] = ':';
}
}
}
if(res < MIN) {
strcpy(ans, tep);
MIN = res;
}
else if(res == MIN) {
if(strcmp(ans, tep) > 0) {
strcpy(ans, tep);
}
}
}
printf("Case #%d: ", cas++);
printf("%s
", ans);
}
return 0;
}
【C】 Palindrome Mouse 回文自动机
回文自动机套模板。
#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 = 100005;
const int N = 26;
ll ans, res;
struct Palindromic_Tree {
int nxt[maxn][N]; // next指针，next指针和字典树类似，指向的串为当前串两端加上同一个字符构成
int fail[maxn]; // fail指针，失配后跳转到fail指针指向的节点
ll cnt[maxn]; // 表示节点i表示的本质不同的串的个数（建树时求出的不是完全的，最后count()函数跑一遍以后才是正确的）
int num[maxn]; // 表示以节点i表示的最长回文串的最右端点为回文串结尾的回文串个数
int len[maxn]; // len[i]表示节点i表示的回文串的长度（一个节点表示一个回文串）
int S[maxn]; // 存放添加的字符
int last; // 指向新添加一个字母后所形成的最长回文串表示的节点。
int n; // 表示添加的字符个数。
int p; // 表示添加的节点个数。
int vis[maxn];
int newnode(int l) {// 新建节点
for(int i = 0; i < N; ++i)
nxt[p][i] = 0;
cnt[p] = 0;
num[p] = 0;
len[p] = l;
vis[p] = 0;
return p++;
}
void init() { // 初始化
p = 0;
newnode(0);
newnode(-1);
last = 0;
n = 0;
S[n] = -1; // 开头放一个字符集中没有的字符，减少特判
fail[0] = 1;
}
int get_fail(int x) { // 和KMP一样，失配后找一个尽量最长的
while(S[n-len[x]-1] != S[n]) x = fail[x];
return x;
}
void add(int c) {
c -= 'a';
S[++n] = c;
int cur = get_fail(last); // 通过上一个回文串找这个回文串的匹配位置
if(!nxt[cur][c]) { // 如果这个回文串没有出现过，说明出现了一个新的本质不同的回文串
int now = newnode(len[cur]+2); // 新建节点
fail[now] = nxt[get_fail(fail[cur])][c]; // 和AC自动机一样建立fail指针，以便失配后跳转
nxt[cur][c] = now;
num[now] = num[fail[now]] + 1;
}
last = nxt[cur][c];
cnt[last] ++;
}
void dfs(int x) {
stack<int> s;
int y = fail[x];
while(y > 1 && vis[y] == 0) {
res ++;
s.push(y);
vis[y] = 1;
y = fail[y];
}
if(x > 1) {
ans += res;
vis[x] = 1;
res ++;
}
for(int i = 0; i < 26; i++) {
if(nxt[x][i]) {
dfs(nxt[x][i]);
}
}
if(x > 1) {
vis[x] = 0;
res --;
}
y = x;
while(!s.empty()) {
res --;
vis[s.top()] = 0;
s.pop();
}
}
}T;
int main() {
string a;
int t;
int cas = 1;
cin >> t;
while(t--) {
cin >> a;
T.init();
int len = a.size();
for(int i = 0; i < len; i++)
T.add(a[i]);
res = ans = 0;
T.dfs(0);
T.dfs(1);
cout << "Case #" << cas++ << ": ";
cout << ans << endl;
}
}
【D】 Move 思维/二分
虽然是数据水所以二分过了，但是我懒得写正解，就这样。
#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 n, k;
int a[maxn];
int sk[maxn];
multiset<int> s;
int solve(int x) {
multiset<int> temp;
temp = s;
for(int i = 1; i <= k; i++) {
int sum = x;
while(sum>0) {
auto it = temp.upper_bound(sum);
if(it == temp.begin()) {
break;
}
it--;
sum -= (*it);
temp.erase(it);
}
if(temp.size() == 0) {
return 1;
}
}
return 0;
}
int main() {
int t, cas = 1;
scanf("%d", &t);
while(t--) {
s.clear();
scanf("%d%d", &n, &k);
for(int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
s.insert(a[i]);
}
int l = 1, r = 1000*1000+5;
int ans = 1;
while(l <= r) {
int mid = (l+r) >> 1;
int res = solve(mid);
if(res == 1) {
ans = mid;
r = mid-1;
}
else {
l = mid+1;
}
}
for(int i = max(0, ans-100); i <= ans; i++) {
if(solve(i)) {
printf("Case #%d: ", cas++);
printf("%d
", i);
break;
}
}
}
return 0;
}
【E】 Androgynos 构造
#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 = 2e3+5;
int mp[maxn][maxn];
int ans[maxn];
int n;
int main() {
int t, cas = 1;
scanf("%d", &t);
while(t--) {
scanf("%d", &n);
printf("Case #%d: ", cas++);
if(n % 4 != 0 && n % 4 != 1) {
printf("No
");
}
else {
printf("Yes
");
int k = n / 4;
memset(mp, 0, sizeof(mp));
/*
团 1 独立集 2 独立集 3 团 4
*/
// 团 1 内部
for(int i = 1; i <= k; i++) {
for(int j = 1; j <= k; j++) {
if(i != j) {
mp[i][j] = mp[j][i] = 1;
}
}
}
// 团 1 --> 独立集 2
for(int i = 1; i <= k; i++) {
for(int j = k+1; j <= 2*k; j++) {
mp[i][j] = mp[j][i] = 1;
}
}
// 独立集 2 --> 独立集 3
for(int i = k+1; i <= 2*k; i++) {
for(int j = 2*k+1; j <= 3*k; j++) {
mp[i][j] = mp[j][i] = 1;
}
}
// 独立集 3 --> 团 4
for(int i = 2*k+1; i <= 3*k; i++) {
for(int j = 3*k+1; j <= 4*k; j++) {
mp[i][j] = mp[j][i] = 1;
}
}
// 团 4 内部
for(int i = 3*k+1; i <= 4*k; i++) {
for(int j = 3*k+1; j <= 4*k; j++) {
if(i != j) {
mp[i][j] = mp[j][i] = 1;
}
}
}
// 1 2 3 4 ---> ans[i] = 2 4 1 3
for(int i = 1; i <= k; i++) {
ans[i] = i+k;
ans[i+k] = i+3*k;
ans[i+2*k] = i;
ans[i+3*k] = i+2*k;
}
// 多出来的点连向两个团 1 4 即可
if(n % 4 == 1) {
for(int i = 1; i <= k; i++) {
mp[i][n] = mp[n][i] = 1;
}
for(int i = 3*k+1; i <= 4*k; i++) {
mp[i][n] = mp[n][i] = 1;
}
ans[n] = n;
}
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= n; j++) {
printf("%d", mp[i][j]);
}
printf("
");
}
for(int i = 1; i <= n; i++) {
printf("%d%c", ans[i], i==n?'
':' ');
}
}
}
return 0;
}
【G】 Is Today Friday? 暴力
#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 n;
string str[maxn];
int ord[10];
int check(int x) {
int year = ord[str[x][0]-'A']*1000 + ord[str[x][1]-'A']*100 + ord[str[x][2]-'A']*10 + ord[str[x][3]-'A'];
int month = ord[str[x][5]-'A']*10 + ord[str[x][6]-'A'];
int day = ord[str[x][8]-'A']*10 + ord[str[x][9]-'A'];
int d_max;
if(month==1 || month==3 || month==5 || month==7 || month==8 || month==10 || month==12) {
d_max = 31;
}
else if(month==4 || month==6 || month==9 || month==11) {
d_max = 30;
}
else if(month==2 && ((year%4==0 && year%100!=0) || year%400==0)) {
d_max = 29;
}
else {
d_max = 28;
}
if(year<1600 || year>9999 || month<1 || month>12 || day<1 || day>d_max) {
return 0;
}
if(month==1 || month==2) {
year--;
month += 12;
}
int w = (day + 2*month + 3*(month+1)/5 + year + year/4 - year/100 + year/400) % 7 + 1;
if(w == 5) {
return 1;
}
return 0;
}
int main() {
int t, cas = 1;
scanf("%d", &t);
while(t--) {
for(int i = 0; i < 10; i++) {
ord[i] = i;
}
scanf("%d", &n);
for(int i = 1; i <= n; i++) {
cin >> str[i];
}
sort(str+1, str+1+n);
n = unique(str+1, str+1+n) - (str+1);
int ok = 0;
do {
ok = 1;
for(int i = 1; i <= n; i++) {
if(check(i) == 0) {
ok = 0;
break;
}
}
if(ok) {
break;
}
}while(next_permutation(ord, ord+10));
printf("Case #%d: ", cas++);
if(ok == 0) {
printf("Impossible
");
}
else {
for(int i = 0; i < 10; i++) {
printf("%d", ord[i]);
}
printf("
");
}
}
return 0;
}
【J】 Upgrading Technology 贪心
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long ll;
const int maxn=1019;
const ll INF = 1ll*(1e9)*(1e5);
ll a[maxn][maxn],d[maxn];
ll pre[maxn][maxn];
ll P[maxn];
ll tail[maxn];
int n,m;
ll minn;
ll ans1,ans2,minj;
int main(){
int T;
scanf("%d",&T);
int kase=1;
while(T--){
scanf("%d%d",&n,&m);
memset(pre,0,sizeof(pre));
memset(P,0,sizeof(P));
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
scanf("%lld",&a[i][j]);
}
}
for(int i=1;i<=m;i++){
scanf("%lld",&d[i]);
}
for(int i=1;i<=m;i++){
for(int j=1;j<=n;j++){
P[i]-=a[j][i];
}
P[i]=P[i-1]+P[i]+d[i];
}
memset(tail,0,sizeof(tail));
//tail[n]!
ll ans=P[m];
for(int i=m-1;i>=0;i--){
int flag=0;minn=-INF;
for(int j=1;j<=n;j++){
if(tail[j]+a[j][i+1]<=0){
tail[j]+=a[j][i+1];
P[i]-=tail[j];
if(minn<=tail[j]){
minn=tail[j];
minj=j;
}
}
else{
tail[j]=0;
flag=1;
}
}
if(!flag){
tail[minj]=0;
P[i]+=minn;
}
ans=max(ans,P[i]);
}
if(ans<0) ans=0;
printf("Case #%d: %lld
",kase++,ans);
}
}