20160813 训练记录
P1. 给出字符串，求它删除后缀后的字符串是什么。删除的后缀为'ly', 'ing', 'er'。最多删除一个后缀。
$|S| <= 32$
【题解】无可奉告
# include <stdio.h>
# include <stdlib.h>
# include <algorithm>
# include <string.h>
# include <math.h>
# include <string>
# include <iostream>
using namespace std;
char str[100010];
int main() {
freopen("suffix.in", "r", stdin);
freopen("suffix.out", "w", stdout);
while(~scanf("%s", str)) {
int sz = strlen(str);
if(sz > 1 && str[sz-1] == 'r' && str[sz-2] == 'e') {
str[sz-2] = '\0';
} else if(sz > 1 && str[sz-1] == 'y' && str[sz-2] == 'l') {
str[sz-2] = '\0';
} else if(sz > 2 && str[sz-1] == 'g' && str[sz-2] == 'n' && str[sz-3] == 'i') {
str[sz-3] = '\0';
}
puts(str);
}
return 0;
}
P2. 砝码称重
【题解】二进制拆分
# include <stdio.h>
# include <stdlib.h>
# include <algorithm>
# include <string.h>
# include <math.h>
# include <string>
# include <iostream>
using namespace std;
int a[7];
int fm[7] = {0, 1, 2, 3, 5, 10, 20};
int b[66666], bn=0;
bool f[200010];
int main() {
freopen("weight.in", "r", stdin);
freopen("weight.out", "w", stdout);
for (int i=1; i<=6; ++i) {
scanf("%d", &a[i]);
int j=0;
while(a[i] - (1<<j) >= 0) {
a[i] = a[i] - (1<<j);
b[++bn] = fm[i] * (1<<j);
++j;
}
if(a[i] != 0) {
b[++bn] = fm[i] * a[i];
}
}
/*
for (int i=1; i<=bn; ++i) printf("%d ", b[i]);
printf("\n");
*/
f[0]=1;
for (int i=1; i<=bn; ++i)
for (int j=100000; j>=1; --j)
if(j-b[i] >= 0) {
f[j] |= f[j-b[i]];
}
int ans=0;
for (int i=1; i<=100000; ++i) {
//if(f[i]) printf("%d\n", i);
ans+=f[i];
}
printf("Total=%d\n", ans);
return 0;
}
P3. hopscotch
给出一个$n \times m$的矩阵，求从左上角走到右下角有几种走法。
走的规则是：满足下列2个条件，就可以从$(x,y)$走到$(i, j)$。
1. $i>x, j>y$
2. $a_{i,j} \not= a_{x,y}$
对于60%，$n \leq 100$
对于100%，$n \leq 750, a_{i,j} \leq n \times m$
【题解】啊这么难的题目出在第三题意义不明啊。
暴力能拿70
# include <stdio.h>
# include <stdlib.h>
# include <algorithm>
# include <string.h>
# include <math.h>
# include <string>
# include <iostream>
# include <vector>
# define PB push_back
# define MP make_pair
using namespace std;
int n, m, a[760][760], k;
long long f[760][760], s[760][760];
const long long MOD=1e9+7;
vector< pair<int, int> > v[666666];
int main() {
freopen("hopscotch.in", "r", stdin);
freopen("hopscotch.out", "w", stdout);
scanf("%d%d%d", &n, &m, &k);
for (int i=1; i<=k; ++i) v[i].clear();
for (int i=1; i<=n; ++i)
for (int j=1; j<=m; ++j) {
scanf("%d", &a[i][j]);
v[a[i][j]].PB(MP(i, j));
}
for (int i=1; i<=k; ++i) sort(v[i].begin(), v[i].end());
f[1][1]=1;
for (int i=1; i<=n; ++i) s[i][1] = s[1][i] = 1;
for (int i=2; i<=n; ++i)
for (int j=2; j<=m; ++j) {
f[i][j] = s[i-1][j-1];
// printf("%d %d %d %d\n", i, j, a[i][j], f[i][j]);
for (int k=0; k<v[a[i][j]].size(); ++k) {
if(v[a[i][j]][k].first >= i) break;
if(v[a[i][j]][k].first == i-1 && v[a[i][j]][k].second > j) break;
if(v[a[i][j]][k].second >= j) continue;
f[i][j] = f[i][j] - f[v[a[i][j]][k].first][v[a[i][j]][k].second];
f[i][j] = (f[i][j] + MOD) % MOD;
}
// printf("f[i][j] second, %d\n", f[i][j]);
s[i][j] = (s[i-1][j] + s[i][j-1] % MOD - s[i-1][j-1] + MOD) % MOD + f[i][j];
s[i][j] = s[i][j] % MOD;
// printf("s[i][j], %d\n", s[i][j]);
/*
for (int ii=i-1; ii>=1; --ii)
for (int jj=j-1; jj>=1; --jj)
if(a[i][j] != a[ii][jj]) {
f[i][j] += f[ii][jj];
f[i][j] %= MOD;
// if(ii == n && jj == m) printf("i=%d, j=%d\n, a[i][j] = %d, a[ii][jj] = %d\n", i, j, a[i][j], a[ii][jj]);
}
*/
}
for (int i=1; i<=n; ++i, printf("\n"))
for (int j=1; j<=m; ++j) printf("%d ", f[i][j]);
cout << f[n][m] << endl;
return 0;
}
首先我们用一个动态开点的权值线段树的东西。
什么是动态开点？
本来线段树都是一开始build一下建完了，现在是边插入边建
由于线段树插入一个数，其他的数的形态并不需要改变，所以就行啦。
大概insert的最重要的步骤如下（动态开节点）
if(! root) （还没有开节点） root=++tot; （新开节点）
具体可以见代码呀
这题dp是$O(n^4)$挺好想出来的，然后用减法原理变成一个类似于二维前缀和减去一些相等的dp值
那么用动态开点权值线段树就恰好能解决。时间复杂度$O(n^2logn)$
# include <stdio.h>
# include <stdlib.h>
using namespace std;
int n, m, k;
long long f[760][760], s[760][760];
int a[760][760];
const int M=760*760*4, MOD = 1e9+7;
int lc[7000010], rc[7000010], num[7000010], root[M], tot=0;
inline void insert(int &rt, int l, int r, int pos, int val) {
if(!rt) rt=++tot;
if(l == r && l == pos) {
num[rt] = num[rt] + val;
num[rt] %= MOD;
return ;
}
int mid = l+r >> 1;
if(pos <= mid) insert(lc[rt], l, mid, pos, val);
else insert(rc[rt], mid+1, r, pos, val);
num[rt] = num[lc[rt]] + num[rc[rt]];
num[rt] %= MOD;
}
inline int query(int rt, int l, int r, int pos) {
if(!rt) return 0;
if(r <= pos) return num[rt];
int mid = (l+r) >> 1, anss=0;
if(lc[rt]) anss = (anss + query(lc[rt], l, mid, pos)) % MOD;
if(rc[rt] && pos >= mid+1) anss = (anss + query(rc[rt], mid+1, r, pos)) % MOD;
return anss;
}
int main() {
freopen("hopscotch.in", "r", stdin);
freopen("hopscotch.out", "w", stdout);
scanf("%d%d%d", &n, &m, &k);
for (int i=1; i<=n; ++i)
for (int j=1; j<=m; ++j) scanf("%d", &a[i][j]);
f[1][1] = 1;
for (int i=1; i<=n; ++i)
s[1][i] = s[i][1] = 1;
insert(root[a[1][1]], 1, m, 1, 1);
for (int i=2; i<=n; ++i) {
for (int j=2; j<=m; ++j) {
f[i][j] = s[i-1][j-1];
//printf("i=%d, j=%d\n", i, j);
// sub
int gg = query(root[a[i][j]], 1, m, j-1);
//printf("i=%d, j=%d, s[i-1][j-1]=%d, sub=%d\n", i, j, s[i-1][j-1], gg);
//printf("%d\n", gg);
f[i][j] = ((f[i][j] - gg) % MOD + MOD) % MOD;
//printf("f[i][j]=%d\n",f[i][j]);
s[i][j] = f[i][j];
s[i][j] = (s[i][j] + s[i-1][j]) % MOD;
s[i][j] = (s[i][j] + s[i][j-1]) % MOD;
s[i][j] = ((s[i][j] - s[i-1][j-1]) % MOD + MOD) % MOD;
}
for (int j=2; j<=m; ++j)
insert(root[a[i][j]], 1, m, j, f[i][j]);
}
printf("%d\n", f[n][m]);
return 0;
}
P4. alphabet
给出一棵树，树上每个点有一个字母，给出一个字符串，问树上是否找得到一条路径对应的字符串是这个。
$n \leq 10000, T \leq 5$
【题解】垃圾题目毁我青春
你没有看错这题就是暴力，复杂度$O(Tn^2)$
# include <stdio.h>
# include <stdlib.h>
# include <algorithm>
# include <string.h>
# include <math.h>
# include <string>
# include <iostream>
# include <queue>
using namespace std;
int T, n, TT;
int tot=0, next[666666], to[666666], head[666666];
char str[666666], qu[666666];
int qs=0;
bool alphause[222];
bool FIND;
inline void add(int u, int v) {
++tot;
next[tot]=head[u];
head[u]=tot;
to[tot]=v;
}
inline void go(int x, int now) {
if(FIND) return;
if(now == qs) {
FIND=1;
return;
}
for (int i=head[x]; i; i=next[i]) {
if(str[to[i]] == qu[now+1]) {
go(to[i], now+1);
if(FIND) return;
}
}
}
int main() {
freopen("alphabet.in", "r", stdin);
freopen("alphabet.out", "w", stdout);
scanf("%d", &T); TT=T;
while(T--) {
memset(head, 0, sizeof(head));tot=0;FIND=0;
memset(alphause, 0, sizeof(alphause));
scanf("%d", &n);
for (int i=1, u, v; i<n; ++i) {
scanf("%d%d", &u, &v);
add(u, v);
add(v, u);
}
scanf("%s", str+1);
scanf("%s", qu+1);
for (qs=1; qu[qs]; ++qs); --qs;
for (int i=1; i<=n; ++i) alphause[str[i]]=1;
bool gg=0;
for (int i=1; i<=qs; ++i)
if(!alphause[qu[i]]) {
gg=1;
break;
}
if(gg) {
printf("Case #%d: Impossible\n", TT-T);
continue;
}
int beg, end;
beg = end = 0;
for (int i=1; i<=n; ++i) {
if(str[i] == qu[1]) beg++;
if(str[i] == qu[qs]) end++;
}
if(end < beg) reverse(qu+1, qu+qs+1);
bool ok=0;
for (int i=1; i<=n; ++i) {
if(qu[1] == str[i]) {
go(i, 1);
if(FIND) {
ok=1;
break;
}
}
}
if(FIND) printf("Case #%d: Find\n", TT-T);
else printf("Case #%d: Impossible\n", TT-T);
}
return 0;
}
p5. route
给出一个$n \times m$的矩阵，要你从左上角向右下角走一条路径，每次向右走或者向下走。
求出路径上经过的点的方差的最小值乘路径长度。
$n,m,a_{i,j} \leq 30$
【题解】这种题目一般推推公式就行啦
令$N = n+m-1$
$w = N \sum_{i in route} a_{i}^{2} - ( \sum_{i in route} a_{i})^2$
然后dp转移啦，$f[i, j, sum]$表示到$(i,j)$，和为$sum$的最小值
转移自己想QAQ，时间复杂度$O(n^4)$
考场上傻逼了想成了$O(n^6)$的复杂度
P.S. sps三分过了。。。
# include <stdio.h>
# include <stdlib.h>
# include <algorithm>
# include <string.h>
# include <math.h>
# include <string>
# include <iostream>
using namespace std;
int n, m, a[60][60];
long long f[33][33][2223];
bool can[33][33][2223];
int main() {
freopen("route.in", "r", stdin);
freopen("route.out", "w", stdout);
scanf("%d%d", &n, &m);
for (int i=1; i<=n; ++i)
for (int j=1; j<=m; ++j) scanf("%d", &a[i][j]);
f[1][1][a[1][1]] = (n+m-2)*a[1][1]*a[1][1];
can[1][1][a[1][1]] = 1;
for (int i=1; i<=n; ++i)
for (int j=1; j<=m; ++j) {
if(i==1 && j==1) continue;
for (int k=0; k<=2222; ++k) {
if(k-a[i][j] >= 0) {
bool fz=0;
f[i][j][k] = 0;
if(can[i-1][j][k-a[i][j]]) f[i][j][k] = f[i-1][j][k-a[i][j]], fz=1, can[i][j][k] = 1;
if(can[i][j-1][k-a[i][j]]) {
can[i][j][k] = 1;
if(!fz) f[i][j][k] = f[i][j-1][k-a[i][j]], fz=1;
else f[i][j][k] = min(f[i][j][k], f[i][j-1][k-a[i][j]]);
}
if(fz == 0) continue;
f[i][j][k] += (k-a[i][j])*(k-a[i][j]) + (n+m-1)*a[i][j]*a[i][j] - k*k;
f[i][j][k] = max(f[i][j][k], 0LL);
}
}
}
/*
for (int i=1; i<=n; ++i)
for (int j=1; j<=m; ++j)
for (int k=0; k<=10; ++k) printf("i=%d, j=%d, k=%d, f[i][j][k] = %d\n", i, j, k, f[i][j][k]);
*/
long long ans = 7777777778888888LL;
for (int k=0; k<=2222; ++k) if(f[n][m][k] != 0) ans = min(ans, f[n][m][k]);
cout << ans << endl;
return 0;
}
/*
N=n+m-1;
w=sigma(N*(ai-sum/N)^2).
w=sigma(N*(ai^2+sum^2/N^2-2*ai*sum/N))
w=sigma(N*ai^2 + sum^2/N - 2*ai*sum)
w=N sigma ai^2 - sum^2
*/
2023年6月17日 13:53
Our team is made up of professional writers and citizen journalists with a wide range of journalism interests who are passionate about reporting Education Updates with transparency in the general public interest.ekhan is a group of ekhan.in professional writers who have banded together to provide devoted news coverage of current events in India. Our team is made up of professional writers and citizen journalists with a wide range of journalism interests who are passionate about reporting Education Updates with transparency in the general public interest.