20240720周赛订正
总结
本场比赛没有任何少拿的分。
题解
T1
尺取。
# include <bits/stdc++.h>
using namespace std;
typedef long long ll;
// # define int long long
# define lc u << 1
# define rc u << 1 | 1
# define fi first
# define se second
const int N = 1000005;
int n;
int m[N], c[N];
struct node
{
int val, row;
bool operator < (const node &t) const { return val < t.val; }
} a[N]; int tot;
int cnt[N];
signed main ()
{
scanf ("%d", &n);
for (int i = 1; i <= n; i ++ )
{
scanf ("%d%d", &m[i], &c[i]);
for (int j = 1; j <= m[i]; j ++ )
{
int x; scanf ("%d", &x);
a[ ++ tot] = {x, i};
}
}
sort (a + 1, a + 1 + tot);
int full = 0;
int ans = 1e9;
for (int i = 1, j = 1; i <= tot; i ++ )
{
while (j <= tot && full < n)
{
cnt[a[j].row] ++ ;
if (cnt[a[j].row] == c[a[j].row]) full ++ ;
j ++ ;
}
if (full == n) ans = min (ans, a[j - 1].val - a[i].val);
if (cnt[a[i].row] == c[a[i].row]) full -- ;
cnt[a[i].row] -- ;
}
printf ("%d\n", ans);
return 0;
}
T2
随便写
# include <bits/stdc++.h>
using namespace std;
typedef long long ll;
// # define int long long
# define lc u << 1
# define rc u << 1 | 1
# define fi first
# define se second
const int N = 1000005;
int n, m;
bool vis[N];
signed main ()
{
// freopen ("forward.in", "r", stdin);
// freopen ("forward.out", "w", stdout);
int T; scanf ("%d", &T);
while (T -- )
{
scanf ("%d%d", &n, &m);
stack <int> q;
for (int i = n; i >= 1; i -- ) q.push (i), vis[i] = 0;
while (m -- )
{
int x; scanf ("%d", &x);
q.push (x);
}
while (!q.empty ())
{
int u = q.top (); q.pop ();
if (vis[u]) continue;
vis[u] = 1;
printf ("%d ", u);
}
printf ("\n");
}
return 0;
}
T3
容易发现一个数是 \(x\)，后面的一个数就是 \(x\div p\) 或者 \(x \times p\)。
# include <bits/stdc++.h>
using namespace std;
typedef long long ll;
// # define int long long
# define lc u << 1
# define rc u << 1 | 1
# define fi first
# define se second
const int N = 1000005;
int n;
bool com[N];
int pri[N], tot;
int ans[N], anstot;
signed main ()
{
// freopen ("forward.in", "r", stdin);
// freopen ("forward.out", "w", stdout);
int T; scanf ("%d", &T);
while (T -- )
{
scanf ("%d", &n);
int tmp = n;
tot = 0;
for (int i = 2; i * i <= tmp; i ++ )
{
while (tmp % i == 0)
{
tmp /= i;
pri[ ++ tot] = i;
}
}
if (tmp > 1) pri[ ++ tot] = tmp;
sort (pri + 1, pri + 1 + tot);
queue <int> q; q.push (1);
anstot = 0;
map <int, bool> vis; vis[1] = 1;
// continue;
while (!q.empty ())
{
int u = q.front (); q.pop ();
ans[ ++ anstot] = u;
for (int i = 1; i <= tot; i ++ )
{
if (!vis[u / pri[i]] && u % pri[i] == 0)
{
vis[u / pri[i]] = 1;
q.push (u / pri[i]);
break;
}
else if (!vis[u * pri[i]] && n % (u * pri[i]) == 0)
{
vis[u * pri[i]] = 1;
q.push (u * pri[i]);
break;
}
}
}
// random_shuffle (ans + 1, ans + 1 + anstot);
printf ("%d\n", anstot);
for (int i = 1; i <= anstot; i ++ ) printf ("%d ", ans[i]);
printf ("\n");
}
return 0;
}
T4
设 \(f_i\) 表示前 \(i\) 个数的和的种类数。
# include <bits/stdc++.h>
using namespace std;
typedef long long ll;
// # define int long long
# define lc u << 1
# define rc u << 1 | 1
# define fi first
# define se second
inline int read ()
{
int w = 1, s = 0;
char c = getchar ();
for (; c < '0' || c > '9'; w *= (c == '-') ? -1 : 1, c = getchar ());
for (; c >= '0' && c <= '9'; s = 10 * s + (c - '0'), c = getchar ());
return s * w;
}
const int N = 500005, mod = 1e9 + 7;
int n;
ll a[N], sum[N];
map <ll, int> mp;
ll f[N];
signed main ()
{
scanf ("%d", &n); for (int i = 1; i <= n; i ++ ) scanf ("%lld", &a[i]);
for (int i = 1; i <= n; i ++ ) sum[i] = sum[i - 1] + a[i];
ll he = 0;
for (int i = 1; i <= n; i ++ )
{
f[i] = (1 + he) % mod;
if (mp.find (sum[i]) != mp.end ())
he = (he + mod - mp[sum[i]]) % mod;
he = (he + f[i]) % mod;
mp[sum[i]] = f[i];
}
printf ("%lld\n", f[n]);
return 0;
}
T5
不会
T6
首先离线。然后容易发现，每次询问都是单调不减的。
\(up_{i,j}\) 维护 \((i,j)\) 向上可以扩展的最远距离
\(down_{i,j}\) 维护 \((i,j)\) 向下可以扩展的最远距离。
每次 \(O(n)\) 处理信息。
我们还可以发现，每次询问就是要知道区间里的 \(up\) 的最小值，和 \(down\) 的最小值。
# include <bits/stdc++.h>
using namespace std;
typedef long long ll;
// # define int long long
# define lc u << 1
# define rc u << 1 | 1
# define fi first
# define se second
inline int read ()
{
int w = 1, s = 0;
char c = getchar ();
for (; c < '0' || c > '9'; w *= (c == '-') ? -1 : 1, c = getchar ());
for (; c >= '0' && c <= '9'; s = 10 * s + (c - '0'), c = getchar ());
return s * w;
}
const int N = 2005;
int n, m, k;
int a[N][N];
struct Query { int x, y; } Q[N];
int up[N][N], down[N][N];
int mnup[N << 2], mndn[N << 2];
void pushup (int u)
{
mnup[u] = min (mnup[lc], mnup[rc]);
mndn[u] = min (mndn[lc], mndn[rc]);
}
void build (int u, int l, int r, int t)
{
if (l == r)
{
mnup[u] = up[t][l];
mndn[u] = down[t][l];
return;
}
int mid = l + r >> 1;
build (lc, l, mid, t);
build (rc, mid + 1, r, t);
pushup (u);
}
int ansup, ansdown;
void query (int u, int l, int r, int x, int y)
{
if (x <= l && y >= r)
{
ansup = min (ansup, mnup[u]);
ansdown = min (ansdown, mndn[u]);
return;
}
int mid = l + r >> 1;
if (x <= mid) query (lc, l, mid, x, y);
if (y > mid) query (rc, mid + 1, r, x, y);
}
int f[N][N];
int res[N];
bool check (int bc, int y)
{
if (bc > n || bc > m) return 0;
for (int i = max (1, y - bc + 1); i <= m - bc + 1 ; i ++ )
{
ansup = ansdown = 1e9;
query (1, 1, m, i, i + bc - 1);
if (ansup + ansdown - 1 >= bc) return 1;
}
return 0;
}
char s[N];
signed main ()
{
scanf ("%d %d %d", &n, &m, &k);
for (int i = 1; i <= n; i ++ )
{
scanf ("%s", s + 1);
for (int j = 1; j <= m; j ++ )
a[i][j] = s[j] == '.';
}
for (int i = 1; i <= k; i ++ )
{
scanf ("%d %d", &Q[i].x,&Q[i].y);
a[Q[i].x][Q[i].y] = 0;
}
for (int i = 1; i <= n; i ++ )
{
for (int j = 1; j <= m; j ++ )
{
if (a[i][j]) up[i][j] = up[i - 1][j] + 1;
else up[i][j] = 0;
}
}
for (int i = n; i >= 1; i -- )
{
for (int j = 1; j <= m; j ++ )
{
if (a[i][j]) down[i][j] = down[i + 1][j] + 1;
else down[i][j] = 0;
}
}
for (int i = 1; i <= n; i ++ )
{
for (int j = 1; j <= m; j ++)
{
if (a[i][j])
{
f[i][j] = min ({f[i - 1][j - 1], f[i - 1][j], f[i][j - 1]}) + 1;
res[k] = max (res[k] , f[i][j]);
}
}
}
int ans = res[k];
for (int i = k; i >= 1; i -- )
{
a[Q[i].x][Q[i].y] = 1 , res[i] = ans;
up[Q[i].x][Q[i].y] = up[Q[i].x - 1][Q[i].y] + 1;
for (int j = Q[i].x + 1; j <= n; j ++ )
{
if (!a[j][Q[i].y]) break;
up[j][Q[i].y] += up[Q[i].x][Q[i].y];
}
down[Q[i].x][Q[i].y] = down[Q[i].x + 1][Q[i].y] + 1;
for (int j = Q[i].x - 1; j >= 1; j -- )
{
if (!a[j][Q[i].y]) break;
down[j][Q[i].y] += down[Q[i].x][Q[i].y];
}
build (1, 1, m, Q[i].x);
while (check (ans + 1, Q[i].y)) ans ++ ;
}
for (int i = 1; i <= k; i ++ ) printf ("%d\n", res[i]);
return 0;
}