好不容易,现场怼出只有30人过的C题,然后我看了队友D题tle的代码,让我以为不能暴力写D题,思路被带偏,回不到正轨了…其实是队友用了这个东西我却没发现
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn = 1e5 + 10, N = 1e5 + 10;
queue<int> q;
int rt[maxn], ls[maxn * 50], rs[maxn * 50], sum[maxn * 50], cnt;
#define mid (l + r) / 2
void up(int &o, int pre, int l, int r, int k) {
o = ++cnt;
sum[o] = sum[pre] + 1;
ls[o] = ls[pre];
rs[o] = rs[pre];
if (l == r)
return;
if (k <= mid)
up(ls[o], ls[pre], l, mid, k);
else
up(rs[o], rs[pre], mid+ 1, r, k);
}
int qu(int o, int l, int r, int k) {
if (l == r)
return sum[o];
if (k <= mid)
return qu(ls[o], l, mid, k);
return qu(rs[o], mid + 1, r, k);
}
struct ptree{
char s[maxn];
int next[maxn][26],fail[maxn],cnt[maxn],len[maxn], d[maxn];
int last,n,p;
long long res;
ll ans = 0;
inline int newnode(int l){
cnt[p]=0;
len[p]=l;
memset(next[p], 0, sizeof(next[p]));
return p++;
}
inline void init(){
n = last = p = ans = 0;
newnode(0),newnode(-1);
s[n]=-1;
fail[0]=1;
}
inline int FL(int x){
while(s[n-len[x]-1]!=s[n]) x=fail[x];
return x;
}
void add(char c){
c-='a';
s[++n]=c;
int cur=FL(last);
if(!next[cur][c]){
int now=newnode(len[cur]+2);
cnt[now] = 1;
rt[now] = rt[cur];
int FF = next[FL(fail[cur])][c];
fail[now]=next[FL(fail[cur])][c];
next[cur][c]=now;
while (FF > 1) {
if (qu(rt[now], 1, N, FF))
break;
up(rt[now], rt[now], 1, N, FF);
FF = fail[FF];
}
up(rt[now], rt[now], 1, N, now);
ans += sum[rt[now]] - 1;
}
last=next[cur][c];
}
} p;
char s[maxn];
int main(){
int T, Case = 0;
scanf("%d", &T);
while (T--) {
scanf("%s",s);
p.init();
cnt = 0;
for (int i = 0; s[i]; i++)
p.add(s[i]);
printf("Case #%d: %lld\n", ++Case, p.ans);
}
}
DMove
就是这个暴力,让我翻了历史上最大的一次车
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1005;
int n, k, a[maxn];
int ok(int m) {
multiset<int> s;
multiset<int> ::iterator it;
for (int i = 1; i <= n; i++)
s.insert(a[i]);
for (int i = 1; i <= k; i++) {
int v = m;
while (v) {
it = s.upper_bound(v);//查找第一个大于v的位置
if (it == s.begin())//s最小的数大于v
break;
it--;
v -= *it;
s.erase(it);
if (s.empty())
return 1;
}
}
return 0;
}
int main() {
int T, Case = 0;
cin>>T;
while (T--) {
int mx = 0, sum = 0;
cin>>n>>k;
for (int i = 1; i <= n; i++) {
cin>>a[i];
sum += a[i];
mx = max(mx, a[i]);
}
int limit = max(mx, sum / k);
for (int i = limit;; i++)
if (ok(i)) {
printf("Case #%d: %d\n", ++Case, i);
break;
}
}
}
#include<bits/stdc++.h>
using namespace std;
const int maxn = 2010;
char s[maxn][maxn];
int main() {
int T, Case = 0;
scanf("%d", &T);
while (T--) {
int n;
scanf("%d", &n);
printf("Case #%d: ", ++Case);
if (n % 4 > 1) {
puts("No");
continue;
}
puts("Yes");
int m = n / 4 * 4;
for (int i = 1; i <= n; i++) {
s[i][n + 1] = '\0';
for (int j = 1; j <= n; j++)
s[i][j] = '0';
if (i % 4 == 1 || i % 4 == 0) {
if (m != n && i == n) {
for (int j = 1; j <= m; j += 4)
s[i][j] = s[i][j + 4 - 1] = '1';
continue;
}
if (i % 4 == 1)
s[i][i + 1] = '1';
else
s[i][i - 1] = '1';
for (int j = 1; j <= n; j++)
if ((j + 3) / 4 < (i + 3) / 4) {
if (j % 4 <= 1)
s[i][j] = '1';
}
else if ((j + 3) / 4 > (i + 3) / 4)
s[i][j] = '1';
}
else {
s[i][i - 1] = s[i][i + 1] = '1';
for (int j = 1; (j + 3) / 4 < (i + 3) / 4; j += 4)
s[i][j] = s[i][j + 3] = '1';
}
}
for (int i = 1; i <= n; i++)
puts(s[i] + 1);
for (int i = 0; i < n / 4; i++) {
int a = 2 + i * 4;
int b = 4 + i * 4;
int c = 1 + i * 4;
int d = 3 + i * 4;
printf("%d %d %d %d", a, b, c, d);
if (i == n / 4 - 1) {
if (n == m)
puts("");
else
printf(" ");
}
else
printf(" ");
}
if (n != m)
printf("%d\n", n);
}
}