总结
初一第一,竞赛班第二
还可以,为了照顾提高班来的四个同学放了四个水题,可惜他们做的不是很理想,希望他们下次可以获得满意的成绩
这次做的其实是 AtCoder ABC237
A.Not Overflow
一道水题,C++11直接判断即可
有好多同学没开C++11,默哀默哀,希望大家下次不要再出锅了
#include <bits/stdc++.h>
using namespace std;
long long n, l = -2147483648, r = 2147483647;
int main() {
scanf("%lld", &n);
if (l <= n && n <= r) {
printf("Yes");
} else {
printf("No");
}
}
Code From 彬彬
B.Matrix Transposition
很简单,但是需要用到以前被老师骂的一种打法
数据中\(h,w<100000\),总不能开\(100000*100000\)吧...
所以用多少开多少
见代码
#include <bits/stdc++.h>
using namespace std;
long long n,m,x;
int main()
{
cin>>n>>m;
long long a[n+5][m+5];//数据问题,这样开比较保险
memset(a,0,sizeof(a));
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
cin>>a[i][j];
}
}
for(int i=1;i<=m;i++)
{
for(int j=1;j<=n;j++)
{
cout<<a[j][i]<<' ';
}
cout<<endl;
}
}
C.kasaka
先看前后各有多少a,如果后面少于前面,那就不行
为什么?
如果后面少于前面,那我们不能在后面补
反之,我们可以在前面补a
如果没判掉,就看除去头尾a的部分是否回文
#include <bits/stdc++.h>
using namespace std;
string x,y;//STL的字符串
long long t,w,len;
int main()
{
cin>>x;
y=x;//这里,不初始化长度就会越界
len=x.size();
while(x[t]=='a')t++;
while(x[len-w-1]=='a')w++;
if(w<t)
{
cout<<"No"<<endl;
}
else
{
for(int i=t;i<=len-w-1;i++)
{
y[i-t]=x[i];
}//突然想到可以用strstr
for(int i=0;i<len-t-w;i++)//判回文
{
if(y[i]!=y[len-t-w-i-1])
{
cout<<"No"<<endl;
return 0;
}
}
cout<<"Yes"<<endl;
}
}
D.LR insertion
显然是一道链表,利用链表原理,可以优化成\(O(n)\)
关于链表的介绍详见我的超级黑历史
这里我是手写的
#include <bits/stdc++.h>
using namespace std;
struct node {
int l,r;
}a[1000005];
long long n,t;
char c;
int main()
{
a[0].l=-1;
a[0].r=-1;
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>c;
if(c=='L')
{
a[i].l=a[i-1].l;
a[a[i-1].l].r=i;
a[i-1].l=i;
a[i].r=i-1;
if(a[i].l==-1)
{
t=i;
}
}
else
{
a[i].r=a[i-1].r;
a[a[i-1].r].l=i;
a[i-1].r=i;
a[i].l=i-1;
}
}
cout<<t<<' ';
for(int i=t;i!=-1;i=a[i].r)
{
if(a[i].r!=-1)cout<<a[i].r<<' ';
}
}
以上是做出来的
以下是骗分的
E.Skiing
这道题是一道最长路,我打的SPFA只有98分,正解果然又是堆优化dij
98分代码
#include<bits/stdc++.h>
using namespace std;
struct node
{
long long to,w,next;
}a[1000005];
long long n,m,t,x,y,h[200005],b[200005],ans,f[200005];
void add(long long x,long long y)
{
t++;
a[t].to=y;
a[t].w=b[x]-b[y];
if(a[t].w<0)
{
a[t].w*=2;
}
a[t].next=h[x];
h[x]=t;
}
queue<long long>q;
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
scanf("%lld",&b[i]);
f[i]=-1e14;
}
for(int i=1;i<=m;i++){
scanf("%lld%lld",&x,&y);
add(y,x);
add(x,y);
}
q.push(1);
f[1]=0;
while(!q.empty())
{
long long t=q.front();
q.pop();
for(int i=h[t];i;i=a[i].next)
{
if(f[t]+a[i].w>f[a[i].to])
{
f[a[i].to]=f[t]+a[i].w;
q.push(a[i].to);
}
}
}
for(int i=1;i<=n;i++)
{
if(f[i]>ans)ans=f[i];
}
cout<<ans;
}
一顿欺负 DeepSeaSpray,又问了问教练,终于看懂了正解dij是怎么搞的
去问 DeepSeaSpray ,不要问我
监督#include<bits/stdc++.h>
using namespace std;
struct node
{
long long to,w,next;
}a[1000005];
long long n,m,t,x,y,h[200005],b[200005],ans,dis[200005];
void add(long long x,long long y,long long z)
{
t++;
a[t].to=y;
a[t].w=z;
a[t].next=h[x];
h[x]=t;
}
struct nd{
long long x,dis;
bool operator <(const nd &xx)const
{
return dis>xx.dis;
}
nd(long long xx,long long xdis){
x=xx;
dis=xdis;
}
};
priority_queue<nd>p;
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
scanf("%lld",&b[i]);
}
for(int i=1;i<=m;i++){
scanf("%lld%lld",&x,&y);
if(b[x]>b[y])add(y,x,b[x]-b[y]),add(x,y,0);
else add(x,y,b[y]-b[x]),add(y,x,0);
}
p.push(nd(1,0));
memset(dis,127,sizeof(dis));
dis[1]=0;
for(int i=1;i<=n-1;i++)
{
// cout<<t<<endl;
long long t=p.top().x;
p.pop();
for(int j=h[t];j;j=a[j].next)
{
// cout<<a[j].to<<' '<<a[j].w<<endl;
if(dis[t]+a[j].w<dis[a[j].to])
{
dis[a[j].to]=dis[t]+a[j].w;
p.push(nd(a[j].to,dis[a[j].to]));
}
}
}
for(int i=1;i<=n;i++)
{
ans=max(ans,b[1]-b[i]-dis[i]);
}
cout<<ans;
}
F.|LIS| = 3
考场dfs,只有8分
发现就是一个简单DP
设\(f_{i,x,y,z}\)表示前\(i\)个数构成的LIS中,长度为1的LIS结尾最小是\(x\),长度为2的是\(y\),长度为\(3\)的是为\(z\)
如果你知道\(O(nlog_n)\)的LIS做法的话你应该知道满足\(x<y<z\)
所以只要枚举第\(i+1\)个数时令其小于\(z\)就可以保证不会出现长度为\(x(3 < x)\)的LIS,
#include<bits/stdc++.h>
using namespace std;
long long n,m,f[1005][15][15][15],ans;
int main()
{
cin>>n>>m;
f[0][m+1][m+1][m+1]=1;
for(int i=0;i<n;i++)
{
for(int x=1;x<=m+1;x++)
{
for(int y=1;y<=m+1;y++)
{
for(int z=1;z<=m+1;z++)
{
for(int j=1;j<=m;j++)
{
if(j<=x)
{
f[i+1][j][y][z]+=f[i][x][y][z];
f[i+1][j][y][z]%=998244353;
}
else if(j<=y)
{
f[i+1][x][j][z]+=f[i][x][y][z];
f[i+1][x][j][z]%=998244353;
}
else if(j<=z)
{
f[i+1][x][y][j]+=f[i][x][y][z];
f[i+1][x][y][j]%=998244353;
}
}
}
}
}
}
for(int i=1;i<=m;i++)
{
for(int j=i+1;j<=m;j++)
{
for(int k=j+1;k<=m;k++)
{
ans+=f[n][i][j][k];
ans%=998244353;
}
}
}
cout<<ans;
}
我觉得很好理解,所以不讲了
G.Range Sort Query
直接sort六十分走起
#include<bits/stdc++.h>
using namespace std;
long long n,q,x,c,l,r,a[1000005];
bool cmp(long long x,long long y) {
return x>y;
}
int main()
{
cin>>n>>q>>x;
for(int i=1;i<=n;i++)
{
cin>>a[i];
if(a[i]==x)a[i]=1;
else if(a[i]>x)a[i]=2;
else a[i]=0;
}
for(int i=1;i<=q;i++)
{
cin>>c>>l>>r;
if(c==1)
{
sort(a+l,a+r+1);
}
else
{
sort(a+l,a+r+1,cmp);
}
}
for(int i=1;i<=n;i++)
{
if(a[i]==1)
{
cout<<i;
return 0;
}
}
}
后来听说是bt线段树,就不怎么想打了
标签:std,include,int,long,20220505,ABC237,using,main,模拟 From: https://www.cnblogs.com/I-am-joker/p/ABC237.html