codeforces Intel Code Challenge Final Round (Div. 1 + Div. 2, Combined) 题解(A-D)
分类:
IT文章
•
2023-11-08 21:42:18
A. Checking the Calendar
题意:
给你两个星期几,问你非闰年能否有相邻的两月的一号满足前面那月是第一个后面那月是第二个
思路:
水水就过了,就看是不是差0,2,3
/* ***********************************************
Author :devil
************************************************ */
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <stack>
#include <map>
#include <string>
#include <cmath>
#include <stdlib.h>
#define LL long long
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dep(i,a,b) for(int i=a;i>=b;i--)
#define ou(a) printf("%d
",a)
#define pb push_back
#define mkp make_pair
template<class T>inline void rd(T &x)
{
char c=getchar();
x=0;
while(!isdigit(c))c=getchar();
while(isdigit(c))
{
x=x*10+c-'0';
c=getchar();
}
}
#define IN freopen("in.txt","r",stdin);
#define OUT freopen("out.txt","w",stdout);
using namespace std;
const int inf=0x3f3f3f3f;
const int mod=1e9+7;
const int N=1e5+10;
int fun(char s[])
{
if(s[0]=='m') return 1;
if(s[0]=='t'&&s[1]=='u') return 2;
if(s[0]=='w') return 3;
if(s[0]=='t'&&s[1]=='h') return 4;
if(s[0]=='f') return 5;
if(s[0]=='s'&&s[1]=='a') return 6;
return 7;
}
int main()
{
bool f=0;
char s1[10],s2[10];
scanf("%s%s",s1,s2);
int a=fun(s1),b=fun(s2);
if(a==b||b-a==2||b-a==3) f=1;
b+=7;
if(b-a==2||b-a==3) f=1;
printf("%s
",f?"YES":"NO");
return 0;
}
View Code
B. Batch Sort
题意:
给你n*m的矩阵,每行都是一种排列,可以交换一次,可以交换两列
问你是否可以操作完使得每行都升序
思路:
这个还是有点坑的。。
先把不交换列的判了,如果不行的话就必须交换列了
然后就枚举哪两列交换,固定了以后对于每一行,可以先交换两列的那两个数,也可以先任意交换行内两个数
如果这两种情况都不能使得该行升序,就是false了
如果枚举完全都是false,就是no,否则yes
/* ***********************************************
Author :devil
************************************************ */
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <stack>
#include <map>
#include <string>
#include <cmath>
#include <stdlib.h>
#define LL long long
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dep(i,a,b) for(int i=a;i>=b;i--)
#define ou(a) printf("%d
",a)
#define pb push_back
#define mkp make_pair
template<class T>inline void rd(T &x)
{
char c=getchar();
x=0;
while(!isdigit(c))c=getchar();
while(isdigit(c))
{
x=x*10+c-'0';
c=getchar();
}
}
#define IN freopen("in.txt","r",stdin);
#define OUT freopen("out.txt","w",stdout);
using namespace std;
const int inf=0x3f3f3f3f;
const int mod=1e9+7;
const int N=1e5+10;
int a[22][22],n,m;
bool judge(int p,int q)
{
for(int i=1;i<=n;i++)
{
int cnt=0;
for(int j=1;j<=m;j++)
{
int k=j;
if(k==p) k=q;
else if(k==q) k=p;
if(a[i][k]!=j) cnt++;
}
if(cnt<=2) continue;
bool can=1;
int px,py;
cnt=0;
for(int j=1;j<=m;j++)
{
if(a[i][j]==p&&j!=q)
{
can=0;
px=j;
py=q;
swap(a[i][j],a[i][q]);
break;
}
if(a[i][j]==q&&j!=p)
{
can=0;
px=j;
py=p;
swap(a[i][j],a[i][p]);
break;
}
}
for(int j=1;j<=m;j++)
{
int k=j;
if(k==p) k=q;
else if(k==q) k=p;
if(a[i][k]!=j) cnt++;
}
if(!can) swap(a[i][px],a[i][py]);
if(cnt) return 0;
}
return 1;
}
int main()
{
scanf("%d%d",&n,&m);
bool f=1;
for(int i=1;i<=n;i++)
{
int cnt=0;
for(int j=1;j<=m;j++)
{
scanf("%d",&a[i][j]);
if(a[i][j]!=j) cnt++;
}
if(cnt>2) f=0;
}
for(int i=1;i<m;i++)
{
for(int j=i+1;j<=m;j++)
{
if(judge(i,j))
{
f=1;
i=m;
break;
}
}
}
printf("%s
",f?"YES":"NO");
return 0;
}
View Code
C. Ray Tracing
/* ***********************************************
Author :devil
************************************************ */
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <stack>
#include <map>
#include <string>
#include <cmath>
#include <stdlib.h>
#define LL long long
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dep(i,a,b) for(int i=a;i>=b;i--)
#define ou(a) printf("%d
",a)
#define pb push_back
#define mkp make_pair
template<class T>inline void rd(T &x)
{
char c=getchar();
x=0;
while(!isdigit(c))c=getchar();
while(isdigit(c))
{
x=x*10+c-'0';
c=getchar();
}
}
#define IN freopen("in.txt","r",stdin);
#define OUT freopen("out.txt","w",stdout);
using namespace std;
const int inf=0x3f3f3f3f;
const int mod=1e9+7;
const int N=1e5+10;
int a[N],b[N],n,m,k;
LL ans[N];
vector<int>eg1[N],eg2[N],eg3[N],eg4[N];
bool vis1[N],vis2[N],vis3[N],vis4[N];
int main()
{
scanf("%d%d%d",&n,&m,&k);
for(int i=1;i<=k;i++)
{
scanf("%d%d",&a[i],&b[i]);
if(a[i]-b[i]>=0) eg1[a[i]-b[i]].pb(i);
if(a[i]+b[i]<=n) eg1[a[i]+b[i]].pb(i);
if(b[i]-a[i]>=0) eg4[b[i]-a[i]].pb(i);
if(a[i]+b[i]<=m) eg4[a[i]+b[i]].pb(i);
if(a[i]+b[i]-n>=0) eg2[a[i]+b[i]-n].pb(i);
if(n+b[i]-a[i]<=m) eg2[n+b[i]-a[i]].pb(i);
if(a[i]+b[i]-m>=0) eg3[a[i]+b[i]-m].pb(i);
if(a[i]+m-b[i]<=n) eg3[a[i]+m-b[i]].pb(i);
}
LL t=0;
int stx=0,sty=0,edx,edy,fang=1;
while(1)
{
if(!stx)
{
if(vis4[sty]) break;
vis4[sty]=1;
if(fang==1)
{
int d=min(n-stx,m-sty);
edx=stx+d;
edy=sty+d;
for(int i=0;i<eg4[sty].size();i++)
{
int p=eg4[sty][i];
if(b[p]>=sty&&!ans[p]) ans[p]=t+a[p];
}
if(edx==n)
{
if(edy==m) break;
fang=2;
}
else fang=4;
}
else
{
int d=min(sty,n);
edx=stx+d;
edy=sty-d;
for(int i=0;i<eg4[sty].size();i++)
{
int p=eg4[sty][i];
if(b[p]<=sty&&!ans[p]) ans[p]=t+a[p];
}
if(edx==n)
{
if(edy==0) break;
fang=3;
}
else fang=1;
}
t+=edx;
stx=edx;
sty=edy;
}
else if(!sty)
{
if(vis1[stx]) break;
vis1[stx]=1;
if(fang==1)
{
int d=min(n-stx,m-sty);
edx=stx+d;
edy=sty+d;
for(int i=0;i<eg1[stx].size();i++)
{
int p=eg1[stx][i];
if(a[p]>=stx&&!ans[p]) ans[p]=t+b[p];
}
if(edx==n)
{
if(edy==m) break;
fang=2;
}
else fang=4;
}
else
{
int d=min(stx,m);
edx=stx-d;
edy=sty+d;
for(int i=0;i<eg1[stx].size();i++)
{
int p=eg1[stx][i];
if(a[p]<=stx&&!ans[p]) ans[p]=t+b[p];
}
if(edx==0)
{
if(edy==m) break;
fang=1;
}
else fang=3;
}
t+=edy;
stx=edx;
sty=edy;
}
else if(stx==n)
{
if(vis2[sty]) break;
vis2[sty]=1;
if(fang==2)
{
int d=min(n,m-sty);
edx=stx-d;
edy=sty+d;
for(int i=0;i<eg2[sty].size();i++)
{
int p=eg2[sty][i];
if(b[p]>=sty&&!ans[p]) ans[p]=t+stx-a[p];
}
if(edx==0)
{
if(edy==m) break;
fang=1;
}
else fang=3;
}
else
{
int d=min(n,sty);
edx=stx-d;
edy=sty-d;
for(int i=0;i<eg2[sty].size();i++)
{
int p=eg2[sty][i];
if(b[p]<=sty&&!ans[p]) ans[p]=t+stx-a[p];
}
if(edx==0)
{
if(edy==0) break;
fang=4;
}
else fang=2;
}
t=t+stx-edx;
stx=edx;
sty=edy;
}
else
{
if(vis3[stx]) break;
vis3[stx]=1;
if(fang==3)
{
int d=min(m,stx);
edx=stx-d;
edy=sty-d;
for(int i=0;i<eg3[stx].size();i++)
{
int p=eg3[stx][i];
if(a[p]<=stx&&!ans[p]) ans[p]=t+stx-a[p];
}
if(edx==0)
{
if(edy==0) break;
fang=4;
}
else fang=2;
}
else
{
int d=min(m,n-stx);
edx=stx+d;
edy=sty-d;
for(int i=0;i<eg3[stx].size();i++)
{
int p=eg3[stx][i];
if(a[p]>=stx&&!ans[p]) ans[p]=t+a[p]-stx;
}
if(edx==n)
{
if(edy==0) break;
fang=3;
}
else fang=1;
}
t=t+sty-edy;
sty=edy;
stx=edx;
}
}
for(int i=1;i<=k;i++) printf("%I64d
",ans[i]?ans[i]:-1);
return 0;
}