Noip2016 十连测 填坑【Updating】
【Noip2016 十连测填坑专场】
蓝色Title表示还未填坑完成，红色Title表示完成
Round 1
A. String Master
给出两个长度为$n$的字串，求修改$k$次之后的最长公共子串最长是多少
$n, k \leq 300$
【题解】暴力模拟即可，复杂度$O(n^3)$。
# include <stdio.h>
# include <algorithm>
using namespace std;
const int M=310;
int n, k;
char s[M], t[M];
int ans = 0;
int main() {
scanf("%d%d", &n, &k);
scanf("%s%s", s+1, t+1);
for (int i=1; i<=n; ++i)
for (int j=1; j<=n; ++j) {
int cnt = 0, len = 0;
for (int i1=i, i2=j; i1<=n && i2<=n; ++i1, ++i2) {
if(s[i1] != t[i2]) {
if(cnt == k) break;
++cnt;
}
++len;
}
if(len>ans) ans=len;
}
printf("%d\n", ans);
return 0;
}
B. Tourist Attractions
找出$n$个点的图的四元环个数
$n \leq 1500$
【题解】
首先，四元环$a-b-c-d$中，$b-c$对答案的贡献为$(deg_b-1)(deg_c-1)-count(b,c)$，其中$count(b,c)$表示经过$b-c$的三元环个数。
三元环个数只要枚举另外一个顶点即可。所以复杂度是$O(n^3)$。
设$S_b$表示所有与$b$有关的边的集合，所以，三元环个数就是$card(S_b~and~S_c)$。所以我们二进制压位进行运算即可。压20位即可。时间复杂度$O(\frac{n^3}{20})$。
# include <stdio.h>
# include <string.h>
# include <algorithm>
# define COUNT __builtin_popcount
using namespace std;
const int M = 1510;
int n, du[M];
int a[M][M];
char A[M];
typedef long long ll;
typedef unsigned long long ull;
ll ans = 0;
bool vis[M];
int b[M][81], B[81];
int f[1<<20];
/*
inline void dfs(int x, int step) {
if(step==3) {
ans=ans+du[x];
if(a[x][b[0]] == '1') --ans;
if(a[x][b[1]] == '1') --ans;
return ;
}
for (int i=1; i<=n; ++i)
if(!vis[i] && a[x][i]=='1') {
b[step] = i;
vis[i] = 1;
dfs(i, step+1);
vis[i] = 0;
}
}
*/
int main() {
//freopen("tour.in", "r", stdin);
//freopen("tour.out", "w", stdout);
scanf("%d", &n);
for (int i=1; i<=n; ++i) {
scanf("%s", A+1);
b[i][0]=0;
for (int j=1; j<=n; ++j) {
a[i][j] = A[j] - '0';
if((j-1)%20==0) b[i][++b[i][0]]=a[i][j];
else b[i][b[i][0]]=(b[i][b[i][0]]*2)+a[i][j];
if(a[i][j]) du[i]++;
}
}
for (int i=1; i<(1<<20); ++i) f[i] = COUNT(i);
for (int i=1; i<=n; ++i)
for (int j=1; j<=n; ++j)
if(a[i][j] == 1) {
ll t=0;
int to=max(b[i][0], b[j][0]);
for (int k=1; k<=to; ++k) B[k]=b[i][k]&b[j][k];
for (int k=1; k<=to; ++k) t=t+f[B[k]];
ans = ans + (ll)(du[i]-1)*(du[j]-1) - t;
}
/*
for (int i=1; i<=n; ++i) {
b[0]=i;
vis[i] = 1;
dfs(i, 1);
vis[i] = 0;
}
*/
printf("%lld\n", ans);
return 0;
}
C. Walk
有$n$个点，$m$条边，点有点权，连单向边$(i,j)$当且仅当$v_i~and~v_j = v_j$，边权均为1，求从1号点到达其他点的最短路程。
$n \leq 200000, m \leq 300000, v_i \leq 2^{20}$
【题解】
新增$2^20$个点对应权值，每个点向对应的权值的点连边，以及连上$m$条边，其他边在spfa时暴力连上即可（不然会MLE），直接一遍spfa（bfs）。时间复杂度$O(20 \times 2^20 + n + m)$。
# include <stdio.h>
# include <vector>
# include <queue>
# define PB push_back
# define MP make_pair
# define pii pair<int,int>
# define to first
# define we second
// # include <bits/stdc++.h>
using namespace std;
const int N = 200010 + (1<<20) + 1;
vector< pii > G[N];
bool vis[N];
int d[N], val[N];
int n, m;
queue<int>Q;
inline void add(int u, int v, int l) {
// printf("%d %d %d\n", u, v, l);
G[u].PB(MP(v, l));
}
int main() {
int Mx=0;
scanf("%d%d", &n, &m);
for (int i=1; i<=n; ++i) {
scanf("%d", &val[i]); Mx=max(Mx, val[i]);
add(i, val[i]+n+1, 1);
add(val[i]+n+1, i, 0);
d[i] = 1000000001;
}
for (int i=1, u, v; i<=m; ++i) {
scanf("%d%d", &u, &v);
add(u, v, 1);
}
int tsz=1;
while(tsz<Mx) tsz<<=1;
for (int i=n+1; i<=tsz+n; ++i) d[i]=1000000001;
while(!Q.empty()) Q.pop();
Q.push(1);vis[1]=1;d[1]=0;
while(!Q.empty()) {
int top=Q.front();Q.pop();vis[top]=0;
// top>n ? printf("num %d\n", top-n-1) : printf("point %d\n", top);
for (int i=0; i<G[top].size(); i++) {
if(d[top]+G[top][i].we<d[G[top][i].to]) {
d[G[top][i].to]=d[top]+G[top][i].we;
if(!vis[G[top][i].to]) {
vis[G[top][i].to]=1;
Q.push(G[top][i].to);
}
}
}
if(top>n) {
for (int i=0; i<=19; ++i)
if((top-n-1)&(1<<i)) {
int so=(top-n-1)-(1<<i)+n+1;
if(d[top]<d[so]) {
d[so]=d[top];
if(!vis[so]) {
vis[so]=1;
Q.push(so);
}
}
}
}
}
for (int i=1; i<=n; ++i) printf("%d\n", d[i] == 1000000001 ? -1 : d[i]);
return 0;
}
Round 2
Round 3
A. 平均数
一个长度为$n$的数列，询问所有连续子序列中的平均数中，第k小的值。
$n \leq 100000$。
【题解】二分答案$x$，则将所有$a_i$减去$x$，要寻找的就是区间值<0的有多少段，加上前缀和之后用归并排序解决（逆序对）
# include <stdio.h>
// # include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n;
int a[100010];
double ta[100010];
double tmp[100010];
ll ret = 0, k;
inline void merges(int l, int mid, int r) {
int i=l, j=mid+1, k=l;
while(i<=mid && j<=r) {
if(ta[i] > ta[j]) {
tmp[k++] = ta[j++];
ret += mid-i+1;
} else tmp[k++] = ta[i++];
}
while(i<=mid) tmp[k++] = ta[i++];
while(j<=r) tmp[k++] = ta[j++];
for (int i=l; i<=r; ++i) ta[i] = tmp[i];
}
inline void merge(int l, int r) {
if(l<r) {
int mid = l+r>>1;
merge(l, mid);
merge(mid+1, r);
merges(l, mid, r);
}
}
inline bool check(double x) {
ret = 0;
ta[0] = 0.0;
for (int i=1; i<=n; ++i) ta[i] = ta[i-1] + a[i] - x;
merge(0, n);
return ret >= k;
}
int main() {
freopen("ave.in", "r", stdin);
freopen("ave.out", "w", stdout);
scanf("%d%lld", &n, &k);
for (int i=1; i<=n; ++i) scanf("%d", &a[i]);
double mid, l = 0.0, r = 1000000000.0, ans = 0.0;
while(r-l > 1e-6) {
mid = (l+r) / 2.0;
if(check(mid)) r = mid, ans = mid;
else l = mid;
}
printf("%.4lf\n", ans);
return 0;
}
Round 4
Round 5
Round 6
Round 7
Round 8
Round 9
A. 小P的2048
给出一个2048游戏（$n \times n$），要你模拟$m$次操作，到无效操作后停止，问你一共得分。
$1 \leq m \leq 10^6, 2 \leq n \leq 8$
【题解】模拟即可，复杂度$O(mn^2)$。
# include <stdio.h>
// # include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n, m;
ll a[9][9], b[9];
int oktest = 0, space;
ll score = 0;
inline void out() {
puts("=======================");
for (int i=1; i<=n; ++i, puts(""))
for (int j=1; j<=n; ++j) printf("%lld ", a[i][j]);
printf("SPACE = %d\n", space);
puts("=======================");
}
inline void cntspace() {
space = 0;
for (int i=1; i<=n; ++i)
for (int j=1; j<=n; ++j) space += (a[i][j] == 0);
}
int main() {
freopen("game.in", "r", stdin);
freopen("game.out", "w", stdout);
int temx, temy, temz;
scanf("%d%d", &n, &m);
space = n*n-2;
scanf("%d%d%d", &temx, &temy, &temz);
a[temx][temy] = temz;
scanf("%d%d%d", &temx, &temy, &temz);
a[temx][temy] = temz;
while(m--) {
// out();
scanf("%d%d%d", &temx, &temy, &temz);
bool havechange = 0;
if(temx == 3) {
// right
for (int i=1; i<=n; ++i) {
int cur = n+1;
for (int j=1; j<=n; ++j) b[j] = 0;
for (int j=n; j>=1; --j) {
if(a[i][j] == 0) continue;
int last;
for (last = j-1; last >= 1; --last)
if(a[i][last] != 0) break;
if(last == 0) {
b[--cur] = a[i][j];
break;
}
if(a[i][j] != a[i][last]) {
b[--cur] = a[i][j];
j=last;
} else {
b[--cur] = a[i][j] * 2ll;
score += b[cur];
j=last-1;
}
++j;
}
for (int j=1; j<=n; ++j) {
if(b[j] != a[i][j])
havechange = 1;
a[i][j] = b[j];
}
}
cntspace();
} else if(temx == 2) {
// left
for (int i=1; i<=n; ++i) {
int cur = 0;
for (int j=1; j<=n; ++j) b[j] = 0;
for (int j=1; j<=n; ++j) {
if(a[i][j] == 0) continue;
int last;
for (last = j+1; last <= n; ++last)
if(a[i][last] != 0) break;
if(last == n+1) {
b[++cur] = a[i][j];
break;
}
if(a[i][j] != a[i][last]) {
b[++cur] = a[i][j];
j=last;
} else {
b[++cur] = a[i][j] * 2ll;
score += b[cur];
j=last+1;
}
--j;
}
for (int j=1; j<=n; ++j) {
if(b[j] != a[i][j])
havechange = 1;
a[i][j] = b[j];
}
}
cntspace();
// puts("=asdfasdfasdfasdf");
// out();
} else if(temx == 1) {
// down
for (int i=1; i<=n; ++i) {
int cur = n+1;
for (int j=1; j<=n; ++j) b[j] = 0;
for (int j=n; j>=1; --j) {
if(a[j][i] == 0) continue;
int last;
for (last = j-1; last >= 1; --last)
if(a[last][i] != 0) break;
if(last == 0) {
b[--cur] = a[j][i];
break;
}
if(a[j][i] != a[last][i]) {
b[--cur] = a[j][i];
j = last;
} else {
b[--cur] = a[j][i] * 2ll;
score += b[cur];
j = last-1;
}
++j;
}
for (int j=1; j<=n; ++j) {
if(b[j] != a[j][i])
havechange = 1;
a[j][i] = b[j];
}
}
cntspace();
} else {
// up
for (int i=1; i<=n; ++i) {
int cur = 0;
for (int j=1; j<=n; ++j) b[j] = 0;
for (int j=1; j<=n; ++j) {
if(a[j][i] == 0) continue;
int last;
for (last = j+1; last <= n; ++last)
if(a[last][i] != 0) break;
if(last == n+1) {
b[++cur] = a[j][i];
break;
}
if(a[j][i] != a[last][i]) {
b[++cur] = a[j][i];
j=last;
} else {
b[++cur] = a[j][i] * 2ll;
score += b[cur];
j=last+1;
}
--j;
}
for (int j=1; j<=n; ++j) {
if(b[j] != a[j][i])
havechange = 1;
a[j][i] = b[j];
}
}
cntspace();
}
if (! havechange) break;
int pos = 1+temy%space, px, py;
for (int i=1; i<=n; ++i)
for (int j=1; j<=n; ++j)
if(a[i][j] == 0) {
pos --;
if(pos == 0) {
px = i;
py = j;
i = n+1, j = n+1;
}
}
a[px][py] = temz;
++ oktest;
}
printf("%d\n%lld\n", oktest, score);
return 0;
}
B. 小P的序列
给出一个序列，问其的子序列中，美丽值最大的子序列的美丽值是多少。
美丽值的定义为，将序列划分为最少的单调上升/下降连续序列，且第一个连续序列不能是上升的，设这样划分完的最小个数为$x$，那么美丽值计算公式为$\frac{\sum a_i}{x}$。
$n \leq 10^5, a_i \leq 10^9$
【题解】猜想最优的$x$不多于2，那么头尾dp几遍就行了。复杂度$O(nlogn)$。其中dp用线段树维护。
# include <stdio.h>
# include <algorithm>
# include <vector>
using namespace std;
# define rank rnk
int n, a[100010];
vector<int> vec;
int rank[100010], N;
typedef long long ll;
typedef long double ld;
ld ans;
ll f[100010], g[100010], uf[100010], ug[100010];
ll w[1000010];
inline void change(int x, int L, int R, int pos, ll del) {
if(L == R) {
w[x] = max(w[x], del);
return ;
}
int mid = L+R>>1;
if(pos <= mid)
change(x<<1, L, mid, pos, del);
else change(x<<1|1, mid+1, R, pos, del);
w[x] = max(w[x<<1], w[x<<1|1]);
}
inline ll ask(int x, int L, int R, int askl, int askr) {
if(askl <= L && R <= askr) return w[x];
int mid = L+R>>1;
if(askr <= mid) return ask(x<<1, L, mid, askl, askr);
else if(askl > mid) return ask(x<<1|1, mid+1, R, askl, askr);
else {
ll t1 = ask(x<<1, L, mid, askl, mid), t2 = ask(x<<1|1, mid+1, R, mid+1, askr);
return max(t1, t2);
}
}
inline void cmax(ll x, int t) {
ld tx = (ld)x/t;
if(tx > ans) ans = tx;
}
int main() {
scanf("%d", &n);
for (int i=1; i<=n; ++i) {
scanf("%d", &a[i]);
vec.push_back(a[i]);
}
sort(vec.begin(), vec.end());
vector<int>::iterator it = unique(vec.begin(), vec.end());
vec.erase(it, vec.end());
for (int i=1; i<=n; ++i) {
rank[i] = lower_bound(vec.begin(), vec.end(), a[i]) - vec.begin() + 1;
N = max(N, rank[i]);
}
// f 从头，单调上升
for (int i=1; i<=1000000; ++i) w[i] = -1e17;
f[1] = a[1];
change(1, 1, n, rank[1], f[1]);
for (int i=2; i<=n; ++i) {
if(rank[i] > 1) f[i] = ask(1, 1, n, 1, rank[i]-1);
if (f[i] == -1e17) f[i] = 0;
f[i] = f[i] + a[i];
change(1, 1, n, rank[i], f[i]);
}
//for (int i=1; i<=n; ++i) printf("%d ", f[i]);
//puts("");
// g 从头，单调下降
for (int i=1; i<=1000000; ++i) w[i] = -1e17;
g[1] = a[1];
change(1, 1, n, rank[1], g[1]);
for (int i=2; i<=n; ++i) {
if(rank[i] < N) g[i] = ask(1, 1, n, rank[i]+1, N);
if (g[i] == -1e17) g[i] = 0;
g[i] = g[i] + a[i];
change(1, 1, n, rank[i], g[i]);
}
//for (int i=1; i<=n; ++i) printf("%d ", g[i]);
//puts("");
// uf 从尾，单调上升（也就是从头看单调下降）
for (int i=1; i<=1000000; ++i) w[i] = -1e17;
uf[n] = a[n];
change(1, 1, n, rank[n], uf[n]);
for (int i=n-1; i>=1; --i) {
if (rank[i] < N) uf[i] = ask(1, 1, n, rank[i]+1, N);
if (uf[i] == -1e17) uf[i] = 0;
uf[i] = uf[i] + a[i];
change(1, 1, n, rank[i], uf[i]);
}
//for (int i=1; i<=n; ++i) printf("%d ", uf[i]);
//puts("");
// ug 从尾，单调下降（也就是从头看单调上升）
for (int i=1; i<=1000000; ++i) w[i] = -1e17;
ug[n] = a[n];
change(1, 1, n, rank[n], ug[n]);
for (int i=n-1; i>=1; --i) {
if (rank[i] > 1) ug[i] = ask(1, 1, n, 1, rank[i]-1);
if (ug[i] == -1e17) ug[i] = 0;
ug[i] = ug[i] + a[i];
change(1, 1, n, rank[i], ug[i]);
}
//for (int i=1; i<=n; ++i) printf("%d ", ug[i]);
//puts("");
// 前传
for (int i=2; i<=n; ++i)
f[i] = max(f[i], f[i-1]),
g[i] = max(g[i], g[i-1]);
for (int i=n-1; i>=1; --i)
uf[i] = max(uf[i], uf[i+1]),
ug[i] = max(ug[i], ug[i+1]);
// 只有一段的情况
bool only = 0;
for (int i=1; i<=n; ++i)
if(g[n] == a[i]) {
only = 1;
break;
}
if(only) ans = g[n];
else ans = (ld)g[n]/2.0;
cmax(f[n], 1);
// 有中间点
for (int i=1; i<n; ++i) {
cmax(f[i] + uf[i+1], 2);
cmax(f[i] + ug[i+1], 2);
}
printf("%.3lf\n", (double)ans);
}
Round 10
2023年4月19日 16:49
TeachersBadi is a website dedicated to education, students, and teachers.The name 'TeachersBadi' reveals the nature of the site. A dedicated Team for teachers, students, and educators is launching and running the site. teachersbadi.in We enjoy sharing primarily educational material and employee and teacher-related content in the educational area.