2022—SWJTU寒假选拔赛第二场复盘
链接
题目列表
A-傻子楼梯 ?
题目链接 Attempted
队列模拟即可
要转变方向当且仅当不同方向的人已抵达电梯,且该方向的下一个人还未到达电梯
然而从赛场到现在我一直wa在test7上,现在也不知道怎么错的。
#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 n=read();
queue<int> e[2];
FOR(i,1,n){
int t=read(),q=read();
e[q].push(t);
}
int t=0,q=0;
if(e[q^1].front()<e[q].front()) q^=1;
t=e[q].front()+10;e[q].pop();
//cout<<t<<":"<<q<<" ";
while(!e[1].empty()||!e[0].empty()){
if(e[q].empty()||e[q^1].empty()) {//cout<<"!";
if(e[q].empty()){
q^=1;
t=max(t,e[q].front())+10;
e[q].pop();
}else{
t=e[q].front()+10;
e[q].pop();
}
}
else if(e[q].front()<t) {
t=max(t,e[q].front()+10);
e[q].pop();
}else{
if(e[q^1].front()<e[q].front()) q^=1;
t=max(t,e[q].front())+10;
e[q].pop();
}
//cout<<t<<":"<<q<<" ";
}
cout<<t;
}
/*
5
1 1
7 0
8 0
10 0
12 1
*/
#include<iostream>
#include<queue>
using namespace std;
queue<int> q0,q1;
int main()
{
int n;
cin >> n;
while(n --)
{
int a,b;
scanf("%d%d",&a,&b);
if(b == 0) q0.push(a);
else q1.push(a);
}
int ans = 0;
while(q0.size() && q1.size())
{
auto up = q0.front(),down = q1.front();
//printf("up = %d,down = %d\n",up,down);
if(up < down)
{
ans += 10;
while(q0.front() < ans && q0.size())
{
ans = max(ans,q0.front() + 10);
//printf("q0.ans = %d\n",ans);
q0.pop();
}
}
else
{
ans += 10;
while(ans > q1.front() && q1.size())
{
ans = max(ans,q1.front() + 10);
//printf("q1.ans = %d\n",ans);
q1.pop();
}
}
}
ans += 10;
int res = 0;
while(q0.size())
{
res = q0.front() + 10;
q0.pop();
}
while(q1.size())
{
res = q1.front() + 10;
q1.pop();
}
printf("%d\n",max(res,ans));
return 0;
}
B-cold爱吃小蛋糕√
题目链接
AC
\(Cold\) 可以无限次吃蛋糕,每次吃掉蛋糕的重量是一个正整数且任意,只要并且不会超过原本蛋糕重量的一半。因为可以无限次合并蛋糕。所以,可以贪心的考虑将所有蛋糕合并,然后次多次将蛋糕吃到 \(K\) 的重量,然后再最后吃一口最重的就是最优解。
也就是,会浪费 \(\frac{K}{2}\) 上取整重量的蛋糕。
#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++)
int main(){
int n=read(),k=read();
ll sum=0;
FOR(i,1,n){
int x=read();
sum+=x;
}
if(sum<k){
cout<<0;
return 0;
}
cout<<sum-min((k+1)/2,(k+2)/2);//这个min不需要 (k+1)/2 表示吃剩的
}
C-郑老板玩方块√
题目链接
AC
题目重述:判断给出的八个坐标能否构成正方体
最开始看到这个大模拟我是非常不想做的,但是看了其他题不是很有把握以及榜单上很多人这道题就写完了(神仙速度)然后就花了不少时间(30min?)把这个搞了出来。
因为只有500组数据,时间很宽裕,我就用了个O(T88*8)的暴力:对于每个点,计算其他七个点与它的距离(直接不用开方),用距离进行个冒泡排序,再判断该点与该点最近的三个点构成的向量长度是否相等,是否垂直。
#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[9][4],b[9][4];
void solve(){
double di;
for(int i=1;i<=8;i++){
FOR(j,1,3)
a[i][j]=read();
}
int f=0;
for(int i=1;i<=8;i++){
FOR(j,1,8){
b[j][1]=a[j][1]-a[i][1];
b[j][2]=a[j][2]-a[i][2];
b[j][3]=a[j][3]-a[i][3];
b[j][0]=b[j][1]*b[j][1]+b[j][2]*b[j][2]+b[j][3]*b[j][3];
}
FOR(j,1,8)
FOR(k,1,7){
if(b[k][0]<b[k+1][0])continue;
FOR(w,0,3)
swap(b[k][w],b[k+1][w]);
}
if(b[2][0]>0&&b[2][0]==b[3][0]&&b[3][0]==b[4][0]&&
b[2][1]*b[3][1]+b[2][2]*b[3][2]+b[2][3]*b[3][3]==0&&
b[3][1]*b[4][1]+b[3][2]*b[4][2]+b[3][3]*b[4][3]==0&&
b[2][1]*b[4][1]+b[2][2]*b[4][2]+b[2][3]*b[4][3]==0
)
f++;
}
if(f==8)cout<<"YES\n";
else cout<<"NO\n";
}
int main(){
int T=read();
while(T--){
solve();
}
}
D-风神瞳√
题目链接
AC
这是一个最短路模板+无穷背包模板的题目。
首先,用Dij或SPFA跑出出发点 S=1
到每个点的最短距离,对于每个非出发点节点相当于背包的物品:花费时间为
dis[i]*2
、收益为
a[i]
。每个“物品”有无限个,然后无线背包dp就行。
#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 = 3200;
const int MAXM = 3200*2+100;
const int INF = 0x3f3f3f3f;
int n,m;
struct node1{
int to,nxt,val;
}edge[MAXM];int cnt=1,head[MAXN];
struct node2{
int to,val;
inline bool operator <(const node2 &x)const
{
return val>x.val;//这里注意符号要为'>'
}
};
inline void add(int u,int v,int w){
edge[++cnt].to=v;
edge[cnt].val=w;
edge[cnt].nxt=head[u];
head[u]=cnt;
}
int vis[MAXN],dis[MAXN];
priority_queue<node2> q;
void dij(){
int s=1;
memset(dis,0x3f,sizeof(dis));dis[s]=0;
memset(vis,0,sizeof(vis));
q.push((node2){s,0});
while(!q.empty()){
int u=q.top().to;q.pop();
if(vis[u]) continue;
vis[u]=1;
for(int i=head[u];i;i=edge[i].nxt){//cout<<"!";
int v=edge[i].to;
if(dis[v]>dis[u]+edge[i].val){
dis[v]=dis[u]+edge[i].val;// cout<<u<<"->"<<v<<":"<<dis[v]<<endl;
q.push((node2){v,dis[v]});
}
}
}
}
int main()
{
int x,y;
int T;
n=read();m=read();
T=read();
int a[MAXN]={0};
FOR(i,2,n)
a[i]=read();
for(int i=1;i<=m;i++){
x=read();y=read();
add(x,y,1);
add(y,x,1);
}
dij();
int f[3010];
memset(f,0,sizeof(f));
FOR(i,1,T){
FOR(j,2,n){
if(i<dis[j]*2) continue;
f[i]=max(f[i],f[i-(dis[j]<<1)]+a[j]);
}
cout<<f[i]<<" ";
}
return 0;
}
E-cold不会字符串
我一直没想到做法是因为我把题目:“如果给你一个P串,是否能构造出来一个T串使得cold的代码不通过”看为了“如果给你一个T串,是否能构造出来一个P串使得cold的代码不通过”,话说如果这样改能有低于\(O(n^2)\)的做法吗。
题目的意思是已知这么一段错误的代码然后给我们一个匹配串,问能否构造一个串使得这个算法得到的答案是错误的。
很明显这段代码错误的原因在于指针 没有回溯。那么怎样的串我们可以把它 hack 掉呢
倘若 next[i]>0
的一定会被 hack
,学过KMP的同学知道,KMP就是求解前后缀匹配情况即数组回溯进行匹配的,但改错误代码其没有回溯,因此产生了错误。那么知道了这点以后,甚至可以不用求
next
数组了,直接判断串中是否有与 s[1]
相同的,有相同的必然是next>1
了。
#include<bits/stdc++.h>
using namespace std;
char s[100000 + 10];
int main()
{
int n ;
cin >> n;
cin >> s + 1;
int flag = 1;
for(int i = 2; i <= n;i ++)
{
if(s[i] == s[1]) flag = 0;
}
if(flag) cout<<"Correct"<<"\n";
else cout<<"Wrong Answer"<<"\n";
return 0;
}
F-你一定会种树吧2.0
我知道这是个线段树,但我没时间去改模板了。也确实不想写。
#include <bits/stdc++.h>
#define il inline
#define fi first
#define se second
#define int long long
#define pii pair<int, int>
#define pll pair<long, long>
#define pb(x) push_back(x)
#define rep(i,x,y) for(auto i=(x);i<=(y);++i)
#define dep(i,x,y) for(auto i=(x);i>=(y);--i)
#define mem(num) memset(num,0,sizeof num)
#define lowbit(x) ((x)&-(x))
using namespace std;
const int mod = 998244353;
const int maxn = 1e6 + 100;
int n, m;
int a[maxn];
struct node{
int l, r;
int mx;
int flag;
} sgt[maxn<<2];
int judge(int x){
return bitset<32>(x).count() == 0;
}
void push_up(int x){
sgt[x].mx = max(sgt[x<<1].mx, sgt[x<<1|1].mx);
sgt[x].flag = sgt[x<<1].flag | sgt[x<<1|1].flag;
}
void build(int x, int l, int r){
if(l == r) {
sgt[x] = {l, r, a[l], a[l]};
return;
}
sgt[x] = {l,r};
int mid = l + r >> 1;
build(x<<1, l, mid); build(x<<1|1, mid + 1, r);
push_up(x);
}
void update(int x, int p, int v){
if(sgt[x].l == p && sgt[x].r == p) {
sgt[x].mx = v;
sgt[x].flag = v;
return;
}
int mid = sgt[x].l + sgt[x].r >> 1;
if(p<=mid) update(x<<1,p,v);
else update(x<<1|1,p,v);
push_up(x);
}
void modify(int x, int l, int r, int v){
if(!((~v)&sgt[x].flag)) return;
if(sgt[x].l == sgt[x].r) {
sgt[x].mx &= v;
sgt[x].flag &= v;
return;
}
int mid = sgt[x].l + sgt[x].r >> 1;
if(l<=mid) modify(x<<1,l,r,v);
if(r>mid) modify(x<<1|1,l,r,v);
push_up(x);
}
inline int query(int x, int l ,int r){
if(sgt[x].l>=l&&sgt[x].r<=r) return sgt[x].mx;
int mid = sgt[x].l + sgt[x].r >> 1;
if (r <= mid)return query(x << 1, l, r);
else if (l > mid)return query(x << 1 | 1, l, r);
else{
int res = 0;
res = max(res,query(x<<1,l,r));
res = max(res,query(x<<1|1,l,r));
return res;
}
}
inline void solve(){
cin >> n;
cin >> m;
for (int i = 1; i <= n; ++ i) {
cin>>a[i];
}
build(1,1,n);
string op;
int l, r, x, v;
for (int i = 1; i <= m; ++ i) {
cin>>op;
if(op[0] == 'A') {
//cout<<1<<endl;
cin>>l>>r>>v;
modify(1,l,r,v);
} else if(op[0] == 'U'){
cin>>x>>v;
update(1,x,v);
} else {
cin>>l>>r;
cout<<query(1,l,r)<<"\n";
}
}
}
signed main(){
std::ios::sync_with_stdio(false);
std::cin.tie(NULL);std::cout.tie(NULL);
int _ = 1;
//cin >> _;
while (_--) {
solve();
}
}
G-郑老板爱玩博弈论√
题目链接
AC
这道题属于是,一看题面长度吓死人,仔细看后可以算,算出来后直觉离谱的题。因为答案就输出一个0.0000
老板对于每个选择都是 \(\frac{1}{20}\) 的概率,我直接写了个程序跑出来,无论学生取什么数字,期望得分都是 \(0\),
#include<bits/stdc++.h>
using namespace std;
int main(){
FOR(a,1,20){
double ans=0;
FOR(x,1,10){
if(a>x)ans+=(x-a+10)/20;
if(a<x)ans+=(x-a-10)/20;
}
//cout<<a<<":"<<ans<<" ";
}
printf("%.4f",0);
}
H-琴
题目链接
Attempted
\(O(T\sqrt{n})\)
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
int main()
{
int T;
cin >> T;
while(T --)
{
LL res = 0x3f3f3f3f;
LL n,m;
scanf("%lld%lld",&n,&m);
if(m % n == 0) puts("0");
else if(n > m) printf("%lld\n",n - m);
else
{
for(LL l = 1,r;l <= n;l = r + 1)
{
r = min(n,(m - 1) / ((m - 1) / l));
res = min(res,((m - 1) / l )* l);
}
printf("%lld\n",n - m + res);
}
}
return 0;
}
I-简单数学2.0
考虑离线莫队。 题目相当于找出每段区间里每个数字的所有因子,找到其出现次数最多的因子的个数。 但是 ai 最大可达到 \(1e^6\), 因子数量太多。仔细想想会发现我们并不需要求出所有因子,只需要求出所有质因子即可,又因为一个数的质因子个数非常少(最多不超过 7 个,记为 \(k\)),因此我们可以预处理所有数的质因子后把问题近似为求区间众数。维护每个质因子出现的次数和出现 i 次的质因子的数量,即可离线后使用莫队求解本题。 由于 n 和 q 为同一数量级,总时间复杂度为 \(O(kn\sqrt{n})\)
#include<bits/stdc++.h>
using namespace std;
const int N=5e4+10, B=220, X=1e6+10;
vector<int> V[X];
int numofp[X], num[N];
int maxp;
int n, m;
int a[N];
bool visp[X];
vector<int> vis;
//prime
void getprime(int i){
if(V[i].size()) return;
int x=i;
for(int j=2; j*j<=x; ++j){
if(x%j==0){
V[i].push_back(j);
while(x%j==0){
x/=j;
}
}
}
if(x>1) V[i].push_back(x);
}
//modui
struct Query{
int l, r, ans, id;
Query(int l=0, int r=0, int id=0):l(l),r(r),id(id){}
bool operator<(const Query&t)const{
int a=l/B, b=t.l/B;
if(a!=b) return a<b;
return r<t.r;
}
}q[N];
void Add(int w){
// printf("%d\n", a[w]);
for(auto&p:V[a[w]]){
// printf("+ %d\n", p);
num[numofp[p]]--;
numofp[p]++;
num[numofp[p]]++;
maxp=max(maxp,numofp[p]);
// printf("maxp=%d\n", maxp);
}
}
void Del(int w){
for(auto&p:V[a[w]]){
num[numofp[p]]--;
numofp[p]--;
num[numofp[p]]++;
if(num[maxp]==0) maxp--;
}
}
int Getans(){
return maxp;
}
bool cmp(const Query&q1, const Query&q2){
return q1.id<q2.id;
}
int main(){
int T; cin>>T;
//init V[]
// getprime();
//solve
while(T--){
//input n, q, a[], query[]
scanf("%d%d", &n, &m);
num[0]=X;
for(int i=1; i<=n; ++i){
scanf("%d", a+i);
getprime(a[i]);
}
for(int i=1, l, r; i<=m; ++i){
scanf("%d%d", &l, &r);
q[i]=Query(l,r,i);
}
q[0]=Query(1,1,0);
//prime factor of a[]
for(int i=1; i<=n; ++i){
for(auto&j:V[a[i]]){
if(!visp[j]){
visp[j]=true;
vis.push_back(j);
}
}
}
//block, sort
sort(q,q+m+1);
//solve
int l=1, r=0;
for(int i=0; i<=m; ++i){
// printf("l=%d r=%d\n", l, r);
while(l<q[i].l) Del(l++);
while(l>q[i].l) Add(--l);
while(r<q[i].r) Add(++r);
while(r>q[i].r) Del(r--);
q[i].ans=Getans();
}
//print
sort(q,q+m+1,cmp);
for(int i=1; i<=m; ++i){
printf("%d\n", q[i].ans);
}
//init
maxp=0;
for(int i=1; i<=n; ++i){
V[i].clear();
num[i]=0;
}
for(auto&i:vis){
visp[i]=false;
numofp[i]=0;
}
vis.clear();
}
}
J-简单水题√
题目链接
AC
看到棋盘格和从左上角走到右下角,只能向右边或者向下行走首先想到递推。
因为每个格子上只能是\(1\)或\(0\),想到可以用路径和表示路过了多少个“\(1\)”和“\(0\)”,为了记录到达每个格子的各种已经路过数量的方案数,对每个格子
\((i,j)\) 还得开个 \(i+j-1\)
来储存各种可能的方案数量。即要开个dp[n][m][n+m]
的三维数组,再在二维上对每个格子dp。
然后我用\(dp[510][510][1050]\)写了出来。然后提交直接 ME。于是想了想,压缩了第一纬度空间。
#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;
const int M = 998244353;
int a[510][510];
int b[2][510][1010];
int main(){
int n=read();
int m=read();
int p=read(),q=read();
FOR(i,1,n)
FOR(j,1,m)
a[i][j]=read();
b[1][1][a[1][1]]=1;
FOR(i,1,n)
FOR(j,1,m){
if(i==1&&j==1) continue;
FOR(k,0,i+j){
b[i%2][j][k]=(b[(i-1)%2][j][k-a[i][j]]+b[i%2][(j-1)][k-a[i][j]])%M;
}
}
int ans=0;
FOR(i,q,n+m-1-p)
ans=(ans+b[n%2][m][i])%M;
cout<<ans;
}
K-学不会的知识*
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1e5 + 10;
map<int, int> M;
int mp[N];
int n, k;
LL a[N];
vector<LL> V;
bool check(int m){
int cnt = 0;
for(auto&i:M){
mp[i.second] = 0;
}
M.clear();
for (int i = 1; i <= n; ++i)
{
int val = a[i];
if (mp[val]){
cnt++;
M.erase(mp[val]);
mp[val] = i;
M[i] = val;
}
else if(M.size()<m){
mp[val] = i;
M[i] = val;
}else{
auto t = M.begin();
int v = t->second;
M.erase(t);
mp[v] = 0;
mp[val] = i;
M[i] = val;
}
}
return cnt >= k;
}
void lisan(){
sort(V.begin(), V.end());
for (int i = 1; i <= n; ++i){
a[i] = lower_bound(V.begin(), V.end(), a[i]) - V.begin()+1;
}
}
int main(){
cin >> n >> k;
for (int i = 1; i <= n; ++i){
scanf("%lld", a + i);
V.push_back(a[i]);
}
lisan();
int l = 1, r = n, mid;
while(l<r-1){
mid = l + r >> 1;
if(check(mid))
r = mid;
else
l = mid + 1;
}
int ans;
if(check(l))
ans = l;
else if(check(r)) ans=r;
else ans=-1;
if(ans>0){
cout << ans << endl;
}else{
cout<<"cbddl"<<endl;
}
}
L-写不完了 *
#include<bits/stdc++.h>
using namespace std;
const int maxm=2e5+5;
int head[maxm],nt[maxm<<1],to[maxm<<1],idx[maxm<<1],cnt;
int d[maxm];
int a[maxm];
int e[maxm];
int n,q;
void add(int x,int y,int z){
cnt++;nt[cnt]=head[x];head[x]=cnt;to[cnt]=y;idx[cnt]=z;
}
void dfs1(int x,int fa){
d[x]=a[x];
for(int i=head[x];i;i=nt[i]){
int v=to[i],w=e[idx[i]];
if(v==fa)continue;
dfs1(v,x);
d[x]=min(d[x],d[v]+w);
}
}
void dfs2(int x,int fa){
for(int i=head[x];i;i=nt[i]){
int v=to[i],w=e[idx[i]];
if(v==fa)continue;
d[v]=min(d[v],d[x]+w);
dfs2(v,x);
}
}
void cal(){
dfs1(1,1);
dfs2(1,1);
int ans=0;
for(int i=1;i<=n;i++){
ans^=d[i];
}
printf("%d\n",ans);
}
void solve(){
scanf("%d%d",&n,&q);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
}
for(int i=1;i<n;i++){
int x,y,z;scanf("%d%d%d",&x,&y,&z);
add(x,y,i);
add(y,x,i);
e[i]=z;
}
while(q--){
int op;scanf("%d",&op);
if(op==1){
int x,y;scanf("%d%d",&x,&y);
a[x]=y;
}else if(op==2){
int x,y;scanf("%d%d",&x,&y);
e[x]=y;
}else{
cal();
}
}
}
signed main(){
solve();
return 0;
}