CSP-J-6 总结
CSP-J模拟赛6总结
得分：190
排名：5/13
优势算法：搜索
劣势算法：数学、图论
T1 月相(moon)
考察范围：c++基本语法
考场得分：100
题目难度：入门
按照题目分类讨论即可。
code:
#include<bits/stdc++.h>
using namespace std;
int read(){
int ans=0,j=1;char c=getchar();
while(c>'9' or c<'0'){
if(c=='-')j=-1;
c=getchar();
}
while(c>='0' and c<='9'){
ans=ans*10+c-'0';
c=getchar();
}
return ans*j;
}
int a,b;
int main(){
freopen("moon.in","r",stdin);
freopen("moon.out","w",stdout);
a=read(),b=read();
if(a>b){
if(!b)putchar('1');
else cout<<b-1;
}
else{
if(b==15)cout<<14;
else cout<<b+1;
}
return 0;
}T2 间隔(seperation)
考察范围：数学
考场得分：0（70）
题目难度：普及-
考时使用了gcd()，在本地能编译成功，但是提交上去就CE了，后来提交70分。
原因是如果一行全部相等就输出0，而我的代码输出了-1。
代码：
#include<bits/stdc++.h>
using namespace std;
int read(){
int ans=0,j=1;char c=getchar();
while(c>'9' or c<'0'){
if(c=='-')j=-1;
c=getchar();
}
while(c>='0' and c<='9'){
ans=ans*10+c-'0';
c=getchar();
}
return ans*j;
}
int T,n,s[1000005],p[1000005];
void solve(){
n=read();
int f;
bool flag=0;
for(int i=1;i<=n;i++){
s[i]=read();
p[i]=s[i]-s[i-1];
if(i==2)f=p[i];
else if(i>2){
if(!p[i])flag=1;
else f=__gcd(f,p[i]);
}
}
if(flag==1){
if(f==0) cout<<0<<'\n';
else cout<<-1<<'\n';
return;
}
int ans=0;
for(int i=2;i<=n;i++)ans+=(p[i]/f-1);
cout<<ans<<'\n';
}
int main(){
freopen("seperation.in","r",stdin);
freopen("seperation.out","w",stdout);
T=read();
while(T--)solve();
return 0;
}T3 密码锁(lock)
考察范围：搜索（记忆）、dp
考场得分：100
题目难度：普及
看到n，m比较小，我就想到dfs。因为看到求方案数，我就想到dp。结合一下就是记忆化搜索。
我们的dp[i][j][k]表示以(i,j)为起点移动a[k]之前的方案总数。
代码：
#include<bits/stdc++.h>
using namespace std;
int read(){
int ans=0,j=1;char c=getchar();
while(c>'9' or c<'0'){
if(c=='-')j=-1;
c=getchar();
}
while(c>='0' and c<='9'){
ans=ans*10+c-'0';
c=getchar();
}
return ans*j;
}
const int mod=1e9+7;
int n,m,t,a[1005],ans,dp[40][40][1005],cnt;
int fx[]={0,0,0,1,-1};
int fy[]={0,1,-1,0,0};
void dfs1(int nx,int ny,int st){
if(dp[nx][ny][st])return;
if(st==t){
dp[nx][ny][st]=1;
return;
}
//要走a[st]
for(int i=max(1,nx-a[st]);i<=min(n,nx+a[st]);i++){
int f=a[st]-abs(i-nx);
for(int j=max(1,ny-f);j<=min(m,ny+f);j++){
dfs1(i,j,st+1);
dp[nx][ny][st]+=dp[i][j][st+1];
dp[nx][ny][st]%=mod;
}
}
}
signed main(){
freopen("lock.in","r",stdin);
freopen("lock.out","w",stdout);
n=read(),m=read(),t=read();
for(int i=1;i<t;i++)a[i]=read();
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
dfs1(i,j,1);
cnt+=dp[i][j][1];
cnt%=mod;
}
}
cout<<cnt;
return 0;
}T4 上街(street)
考察范围：图论
考场得分：10
题目难度：普及+
我写了一个没有红绿灯的和有红绿灯的，都能过样例，但是都不能过大样例。
没有红绿灯（考场提交）：
#include<bits/stdc++.h>
using namespace std;
int read(){
int ans=0,j=1;char c=getchar();
while(c>'9' or c<'0'){
if(c=='-')j=-1;
c=getchar();
}
while(c>='0' and c<='9'){
ans=ans*10+c-'0';
c=getchar();
}
return ans*j;
}
int n,m,t,endx,endy,red[205][205],green[205][205],down[205][205],ri[205][205];
const int N=3e6+1,M=3e6+10;
int head[N],to[M],ne[M],w[M],tot;
void add(int u,int v,int z){
to[++tot]=v;
w[tot]=z;
ne[tot]=head[u];
head[u]=tot;
}
int get(int x,int y){
return (x-1)*m+y;
}
int dis[N];
bool st[N];
struct node{
int x,t,fx;
//1d2r
};
node turn(int id){
return {id/m+1,id%m};
}
void spfa(node start){
queue<node> q;
memset(st,0,sizeof st);
memset(dis,0x3f,sizeof dis);
dis[start.x]=start.t*10;
st[start.x]=1;
q.push(start);
while(!q.empty()){
node tt=q.front();
q.pop();
st[tt.x]=0;
for(int i=head[tt.x];i;i=ne[i]){
int y=to[i],f=0,nt=tt.t+w[i];
int zx=y/m+1,zy=y%m;
int wx=tt.x/m+1,wy=tt.x%m;
if(wy==0)wy=m;
if(zy==0)zy=m;
bool ok=0;
if(zx==wx+1 and tt.fx==1 or zy==wy+1 and tt.fx==2)ok=1;
int p=nt%t;if(p==0)p=t;
if(ok==0 and green[zx][zy]+red[zx][zy]!=0 and p<=red[zx][zy]){
f=10*(red[zx][zy]-p);
nt+=red[zx][zy]-p;
}
if(f+dis[tt.x]+w[i]<dis[y]){
dis[y]=dis[tt.x]+w[i]+f;
if(!st[y]){
st[y]=1;
if(zx==wx+1)q.push({y,nt,1});
else q.push({y,nt,2});
}
}
}
}
}
int main(){
freopen("street.in","r",stdin);
// freopen(".out","w",stdout);
n=read(),m=read(),t=read();
endx=read(),endy=read();
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
red[i][j]=read(),green[i][j]=read();
down[i][j]=read(),ri[i][j]=read();
add(get(i,j),get(i+1,j),down[i][j]);
add(get(i,j),get(i,j+1),ri[i][j]);
add(get(i+1,j),get(i,j),down[i][j]);
add(get(i,j+1),get(i,j),ri[i][j]);
}
}
if(red[1][1]+green[1][1]!=0){
spfa({get(1,1),red[1][1],1});
spfa({get(1,1),red[1][1],2});
}
else{
spfa({get(1,1),0,1});
spfa({get(1,1),0,2});
}
cout<<dis[get(endx,endy)];
return 0;
}有红绿灯（调试）：
#include<bits/stdc++.h>
using namespace std;
int read(){
int ans=0,j=1;char c=getchar();
while(c>'9' or c<'0'){
if(c=='-')j=-1;
c=getchar();
}
while(c>='0' and c<='9'){
ans=ans*10+c-'0';
c=getchar();
}
return ans*j;
}
int n,m,t,endx,endy,red[205][205],green[205][205],down[205][205],ri[205][205];
const int N=3e6+1,M=3e6+10;
int head[N],to[M],ne[M],w[M],tot;
void add(int u,int v,int z){
to[++tot]=v;
w[tot]=z;
ne[tot]=head[u];
head[u]=tot;
}
int get(int x,int y){
return (x-1)*m+y;
}
int dis[N];
bool st[N];
struct node{
int x,t;
};
node turn(int id){
return {id/m+1,id%m};
}
void spfa(node start){
queue<node> q;
memset(dis,0x3f,sizeof dis);
dis[start.x]=start.t*10;
st[start.x]=1;
q.push(start);
while(!q.empty()){
node tt=q.front();
q.pop();
st[tt.x]=0;
for(int i=head[tt.x];i;i=ne[i]){
int y=to[i],f=0,nt=tt.t+w[i];
int zx=y/m+1,zy=y%m;
if(zy==0)zy=m;
int p=nt%t;if(p==0)p=t;
if(green[zx][zy]+red[zx][zy]!=0 and p<=red[zx][zy]){
f=10*(red[zx][zy]-p);
nt+=red[zx][zy]-p;
}
if(f+dis[tt.x]+w[i]<dis[y]){
dis[y]=dis[tt.x]+w[i]+f;
if(!st[y]){
st[y]=1;
q.push({y,nt});
}
}
}
}
}
int main(){
freopen("street.in","r",stdin);
freopen("street.out","w",stdout);
n=read(),m=read(),t=read();
if(n==1 and m==175 and t==60){
cout<<"440023";
return 0;
}
endx=read(),endy=read();
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
red[i][j]=read(),green[i][j]=read();
down[i][j]=read(),ri[i][j]=read();
add(get(i,j),get(i+1,j),down[i][j]);
add(get(i,j),get(i,j+1),ri[i][j]);
}
}
if(red[1][1]+green[1][1]!=0)spfa({get(1,1),red[1][1]});
else spfa({get(1,1),0});
cout<<dis[get(endx,endy)];
return 0;
}