2022—SWJTU寒假选拔赛第三场复盘
一个迟到几周的复盘，现在大年初一才来补题(😓)
链接
题目列表
A-A √
要想让 \(S(x + 1) < s(x)\) 只能可能发生在进位的时候,因此每逢尾数为 \(9\) 时就会对答案产生贡献。
其实通过样例就可以得到解为\((n+1)/10\)
AC code:
#include<bits/stdc++.h>
using namespace std;
inline int read(){
int sum=0,flag=1;char c;
for(;c>'9'||c<'0';c=getchar()) if(c=='-') flag=-1;
for(;c<='9'&&c>='0';c=getchar()) sum=(sum<<3)+(sum<<1)+c-'0';
return flag*sum;
}
#define ll long long
#define FOR(i,a,b) for(int i=(a);i<=(b);i++)
const int MAXN = 32767*2+100;
const int INF = 0x3f3f3f3f;
int main(){
int T=read();
while(T--){
int n=read();
cout<<(n+1)/10<<endl;
}
}B-B √
题目重述；给出 \(1\) 个长度为 \(n\) 的序列，以及 \(1\) 个正整数 \(m\)。问这个原序列中是否存在非空子序列，使其元素之和能被 \(m\) 整除。
看到数据范围数据范围：\(1<=n<=10^6,2<=m<=1000,1<=n<=10\) 。 自然不可能用 \(O(nm)\)，时间复杂度仅仅与\(m\)有关。
考虑 \(n>m\) 的情况：我们对整个数列做前缀和，然后再对 \(m\) 取模。根据抽屉原理，因为 \(n>m\)，所以在 \(n\) 个前缀和中必有两个对 \(m\) 取模于是相等，它们中间那段就是答案。
而 n⩽m 的情况，n⩽103，不会超时,直接 \(O(nm)\) 的背包。
Stl:
#include<bits/stdc++.h>
using namespace std;
#define int long long
inline int read(){int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;
ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+
(x<<3)+(ch^48);ch=getchar();}return x*f;}
#define N 100010
int n, m, i, j, k;
int dp[N], f[N], x;
signed main()
{
n=read(); m=read();
if(n>m) return printf("YES"), 0;
for(i=1; i<=n; ++i)
{
x=read();
for(j=0; j<m; ++j) f[j]=dp[j];
for(j=0; j<m; ++j)
dp[(j+x)%m]+=f[j];
dp[x%m]++; //只有当前x的子集
}
printf("%s", (dp[0] ? "YES" : "NO"));
return 0;
}AC code:
#include <cstdio>
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long int_;
inline int read(){
int a = 0; char c = getchar(), f = 1;
for(; c<'0'||c>'9'; c=getchar())
if(c == '-') f = -f;
for(; '0'<=c&&c<='9'; c=getchar())
a = (a<<3)+(a<<1)+(c^48);
return a*f;
}
inline void writeint(int x){
if(x > 9) writeint(x/10);
putchar((x%10)^48);
}
const int MAXM = 1000;
int gcd[MAXM];
bool dp[MAXM+5];
int cnt[MAXM], dis[MAXM];
int main(){
int n = read(), m = read();
for(int i=0; i<n; ++i)
++ cnt[read()%m];
for(int i=1; i<m; ++i)
if(m%i == 0)
for(int j=1; j<m/i; ++j)
gcd[i*j] = i;
dp[0] = true;
bool ans = cnt[0];
for(int a=1; a<m&&!ans; ++a){
int d = gcd[a];
for(int i=0; i<d; ++i)
for(int j=2*m/d-1; ~j; --j){
int now = (i+j*a)%m;
dis[now] = dis[(now+a)%m]+1;
if(dp[now]) dis[now] = !now;
}
for(int i=0; i<d; ++i)
for(int j=0; j<m/d; ++j){
int now = (i+j*a)%m;
if(dp[now]){
int t = dis[(now+a)%m];
t = min(t,cnt[a]);
for(; t; --t,++j){
now = (now+a)%m;
dp[now] = true;
if(now == 0)
ans = true;
}
}
}
}
puts(ans ? "YES" : "NO");
return 0;
}C-C √
最简单的签到题，直接过
AC code:
#include<bits/stdc++.h>
using namespace std;
inline int read(){
int sum=0,flag=1;char c;
for(;c>'9'||c<'0';c=getchar()) if(c=='-') flag=-1;
for(;c<='9'&&c>='0';c=getchar()) sum=(sum<<3)+(sum<<1)+c-'0';
return flag*sum;
}
#define ll long long
#define FOR(i,a,b) for(int i=(a);i<=(b);i++)
const int MAXN = 32767*2+100;
const int INF = 0x3f3f3f3f;
int main(){
int T=read();
while(T--){
int n=read();
int sum=0;
FOR(i,1,n)
sum+=read();
if(sum>=n)
cout<<sum-n<<endl;
else
cout<<1<<endl;
}
}原D题 √
本来是二维dp题目，硬生生被我做成了字符串（公共子串）匹配，再在得到的二维数组上对公共子串长度记录，再dp（但是我觉得思路更清晰？迷幻）。
AC code:
#include<bits/stdc++.h>
using namespace std;
inline int read(){
int sum=0,flag=1;char c;
for(;c>'9'||c<'0';c=getchar()) if(c=='-') flag=-1;
for(;c<='9'&&c>='0';c=getchar()) sum=(sum<<3)+(sum<<1)+c-'0';
return flag*sum;
}
#define ll long long
#define FOR(i,a,b) for(int i=(a);i<=(b);i++)
const int MAXN = 32767*2+100;
const int INF = 0x3f3f3f3f;
int a[1010][1010];
int d[1010][1010];
int f[1010][1010][13];
//priority_queue <int> q;
//priority_queue <int,vector<int>,greater<int> > q;
//priority_queue <int,vector<int>,less<int> >q;
int main(){
int n,m;
n=read(),m=read();
int r=read();
char s[1010];
char t[1001];
cin>>s+1;
cin>>t+1;
FOR(i,1,n)
FOR(j,1,m)
if(s[i]==t[j])
a[i][j]=1;
FOR(i,1,n)
FOR(j,1,m){
if(a[i][j]==0)
d[i][j]=0;
else
d[i][j]=d[i-1][j-1]+1;
}
int ans=0;
FOR(i,1,n)
FOR(j,1,m)
FOR(k,1,r){
f[i][j][k]=max(f[i-1][j][k],f[i][j-1][k]);
f[i][j][k]=max(f[i][j][k],f[i-d[i][j]][j-d[i][j]][k-1]+d[i][j]);
ans=max(ans,f[i][j][k]);
}
cout<<ans;
}D-E
组合数学，详解见题解
Stl:
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 2e5 + 10;
const int mod = 1e9 + 7;
LL fac[N],inv[N];
LL qmi(LL a, LL k, LL p) // 求a^k mod p
{
LL res = 1 % p;
while (k)
{
if (k & 1) res = res * a % p;
a = a * a % p;
k >>= 1;
}
return res;
}
void fc(int n)
{
inv[0] = fac[0] = 1;
for(int i = 1;i <= n;i ++) fac[i] = (i * fac[i - 1]) % mod,inv[i] = qmi(fac[i],mod - 2,mod);
}
LL c(LL a,LL b)
{
return fac[a] * inv[b] % mod * inv[a - b] % mod;
}
void solve()
{
LL n,k;
cin >> n >> k;
k = min(k,n - 1);
fc(N);
LL res = 0;
for(int i = 0;i <= k;i ++)
res = (res + c(n,i) * c(n - 1,i) % mod) % mod;
cout << res << endl;
}
int main()
{
int T = 1;
//cin >> T;
while(T --)
solve();
return 0;
}E-F
看到这道题我先想到了树形dp、点分治。然而这是个图。
正确思路: 我们已经确定了起点和终点,那么我们只需要枚举 起点到 \(i\) 的距离 + 终点到 \(j\) 的距离 + \(i,j\) 之间的距离判断其是否大于等于最短距离,如果满足那么这个 \(i,j\) 组合就是合法的加边结果。
流程：我们对起点和终点分别跑两次最短路,枚举要加边的两个端点,判断其是否满足条件,计算其对答案的贡献即可。
Stl:
#include<bits/stdc++.h>
using namespace std;
const int N = 1e3 + 10;
int vis[N][N];
vector<int> g[N];
int dist_s[N],dist_t[N];
typedef long long LL;
void solve()
{
int n,m,s,t;
cin >> n >> m >> s >> t;
while(m --)
{
int a,b;
scanf("%d%d",&a,&b);
g[a].push_back(b);
g[b].push_back(a);
vis[a][b] = vis[b][a] = 1;
}
memset(dist_s,- 1,sizeof dist_s);
memset(dist_t,- 1,sizeof dist_t);
queue<int> q;
q.push(s);
dist_s[s] = 0;
while(q.size())
{
auto u = q.front();
q.pop();
for(int i = 0;i < g[u].size();i ++)
{
int v = g[u][i];
if(dist_s[v] == -1) dist_s[v] = dist_s[u] + 1,q.push(v);
}
}
q.push(t);
dist_t[t] = 0;
while(q.size())
{
auto u = q.front();
q.pop();
for(int i = 0;i < g[u].size();i ++)
{
int v = g[u][i];
if(dist_t[v] == -1) dist_t[v] = dist_t[u] + 1,q.push(v);
}
}
LL res = 0;
for(int i = 1;i <= n;i ++)
for(int j = i + 1;j <= n;j ++)
if(!vis[i][j] && dist_s[i] + 1 + dist_t[j] >= dist_s[t] && dist_t[i] + 1 + dist_s[j] >= dist_s[t])
res ++;
cout << res << endl;
}
int main()
{
int T = 1;
while(T --) solve();
return 0;
}F-G
线段树
Stl:
#include <bits/stdc++.h>
using namespace std;
const int maxn=1e6+5;
vector <pair <int,int> >in[maxn],out[maxn];
struct NODE
{
int l,r;
long long sum,num;
} p[maxn*4];
int n,m,k;
void build(int l,int r,int cur)
{
p[cur].l=l;
p[cur].r=r;
p[cur].num=p[cur].sum=0;
if(l==r)
return ;
int mid=(l+r)/2;
build(l,mid,cur*2);
build(mid+1,r,cur*2+1);
}
void pushup(int k)
{
p[k].num=p[k*2].num+p[k*2+1].num;
p[k].sum=p[k*2].sum+p[k*2+1].sum;
}
void update(int num,int pri,int cur)
{
int l=p[cur].l,r=p[cur].r;
if(l==r)
{
p[cur].num+=num;
p[cur].sum+=(long long)num*pri;
return ;
}
int mid=(l+r)/2;
if(pri<=mid)
update(num,pri,2*cur);
else
update(num,pri,2*cur+1);
pushup(cur);
}
long long query(int num,int cur)
{
int l=p[cur].l,r=p[cur].r;
if(l==r)
return (long long)l*min(p[cur].num,(long long)num);
if(num<=p[cur*2].num)
return query(num,cur*2);
else
return p[cur*2].sum+query(num-p[cur*2].num,cur*2+1);
}
int main()
{
int l,r,x,y;
scanf("%d%d%d",&n,&k,&m);
for(int i=0; i<=n; i++)
{
in[i].clear();
out[i].clear();
}
for(int i=1; i<=m; i++)
{
scanf("%d%d%d%d",&l,&r,&x,&y);
in[l].push_back(make_pair(x,y));
out[r].push_back(make_pair(x,y));
}
long long ans=0;
build(1,maxn,1);
for(int i=1; i<=n; i++)
{
for(int j=0; j<in[i].size(); j++)
update(in[i][j].first,in[i][j].second,1);
ans+=query(k,1);
for(int j=0; j<out[i].size(); j++)
update(-out[i][j].first,out[i][j].second,1);
}
printf("%lld\n",ans);
return 0;
}原H题
写了一个二分答案，wa后被告知题目要被删。
G-I √
一个奇葩的题目。你只需要构造出一个满足题意的树就行。
无法构造时： \(d>2h\) 时必定不成立 \(d= 1\) 时,节点数只能是 \(2\)。
先构建成一条满足条件的链,然后不够的再往上加点即可。有一些细节问题，所以我调了很久才A(哭)。
AC code:
#include<bits/stdc++.h>
using namespace std;
inline int read(){
int sum=0,flag=1;char c;
for(;c>'9'||c<'0';c=getchar()) if(c=='-') flag=-1;
for(;c<='9'&&c>='0';c=getchar()) sum=(sum<<3)+(sum<<1)+c-'0';
return flag*sum;
}
#define ll long long
#define FOR(i,a,b) for(int i=(a);i<=(b);i++)
const int MAXN = 32767*2+100;
const int INF = 0x3f3f3f3f;
int n,d,h;
int m=0;
int cnt=1;
int main(){
n=read();d=read();h=read();
if((!(2*h>=d&&d>=h&&n>=d+1))||(d==1&&n>2)){
cout<<-1;
return 0;
}
FOR(i,1,h)
cout<<i<<" "<<++cnt<<endl;
if(h!=d){
cout<<1<<" "<<++cnt<<endl;
FOR(i,2,d-h)
cout<<cnt<<" "<<++cnt<<endl;
}
int o=1;
if(cnt==n) return 0;
if(h==d&&h>1)o=2;
if(h==d&&h==1){
cout<<-1;
return 0;
}
while(cnt!=n){
cout<<o<<" "<<++cnt<<endl;
}
}H-J √
在学长的点拨下做出来的题。
数据范围超空间，所以不能用数组作桶，用map。要用 \(O(n)\)
的做法，要用所以不能存位置，要map存奇数偶数的个数,还要开LL：map<int,ll>
m[2]。导致我写了好几遍。
基本思路：两个相同的数的亦或为\(0\)，\(0\)和任意另外一个数的亦或都为另一个数。
所以对于题目要救“区间从\(1/2\)的位置分割为两部分，两部分的元素异或和相同”，记两段的亦或分别为l，r当且仅当a^l^r=a时满足题意，可得\(O(n)\)的算法（从左到右扫一遍）。
AC code:
#include<bits/stdc++.h>
using namespace std;
inline int read(){
int sum=0,flag=1;char c;
for(;c>'9'||c<'0';c=getchar()) if(c=='-') flag=-1;
for(;c<='9'&&c>='0';c=getchar()) sum=(sum<<3)+(sum<<1)+c-'0';
return flag*sum;
}
#define ll long long
#define FOR(i,a,b) for(int i=(a);i<=(b);i++)
map<int,ll> m[2];
int e;
int main(){
int n=read();
ll ans=0;
m[0][0]++;
FOR(i,1,n){
e=e^read();
ans+=m[i%2][e];//cout<<e<<":"<<m[e][i%2]<<" ";
m[i%2][e]++;
}
cout<<ans;
}I-K
我想了线性dp但我就是没想出来(哭)
让你求解整个序列上的极值问题,然后判断其是否无后效性和是否存在最优子结构就能够知道是不是个 dp ,这题整个序列上的极值显然是可以由其子序列转移而来的,具体证明就不多赘述,直接开始dp。
状态表示：f[i] 表示前 i
个数字中取 \(\frac{n}{2}\)
(向下取整)个数并且这些数两两不相邻,其最大的和。
状态转移：
由于是 \(\frac{n}{2}\) (向下取整)存在奇偶数不同的情况,因此我们对其分类讨论
若是奇数并且选了第 \(i\) 个数则
f[i] = f[i-2] + a[i] ,因为选了第 \(i\) 个数后,第 \(i-1\) 个数就不能被选中了,只能从
f[i-2]转移而来
若没有选第 \(i\) 个数则 f[i] =
f[i-1]
若是偶数并且选了第 \(i\) 个数则同理,
f[i] = f[i-2] + a[i] ,
若没有选第 \(i\)
个数,我们只能将奇数位置上的数全选上才能有 \(⌊n/2⌋\) (向下取整)个数字,不然的话若还是
f[i-1] ,此时 \(i-1\)
为奇数除二下取整会比原来少一个就不符合题目的条件了。
Stl:
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 2e5 + 10;
LL a[N],f[N],s[N];
void solve()
{
int n;
cin >> n;
for(int i = 1;i <= n;i ++) scanf("%lld",&a[i]);
s[1] = a[1];
for(int i = 3;i <= n;i += 2) s[i] = s[i - 2] + a[i];
for(int i = 2;i <= n;i ++)
{
if(i % 2 == 1) //奇数
{
f[i] = max(f[i - 2] + a[i],f[i - 1]);
}
else //偶数
{
f[i] = max(f[i - 2] + a[i],s[i - 1]);
}
}
cout << f[n] << endl;
}
int main()
{
int T = 1;
while(T --)
solve();
return 0;
}