第一届挑战赛标程
wflengxuenong · · 个人记录
T1:
考察基本表达式和最值函数
#include<iostream>
#include<stdio.h>//文件输入输出需要用到的头文件
using namespace std;
int a,b,c,s,ma;
int main(){
freopen("exam.in","r",stdin);
freopen("exam.out","w",stdout);
cin>>a>>b>>c;
s=a+b+c;
ma=max(max(a,b),c);
cout<<s<<" "<<ma<<endl;
return 0;
} T2
/*
考察点1：数字分解，预计得分 40
考察点2：字符数组、ascii码，累加和
*/
#include<bits/stdc++.h>
using namespace std;
int l,sum=0;
char s[10009];
int main(){
freopen("bit.in","r",stdin);
freopen("bit.out","w",stdout);
cin>>l;
cin>>s;//注意用字符串处理，数字的长度已经超过了long long 类型
for(int i=0;i<l;i++){
sum+=s[i]-'0';
}
cout<<sum<<endl;
return 0;
} T3
考察点：容斥。 这道题在考试中得分率比较低，小学生对平面直角坐标系理解和掌握的较少。找矩形的交集对很多考生来说是难点。
/*
1.给定的矩形描述不一定是哪个两个对角线上的点，需要整理成统一的的左上角、右下角描述
2. 部分分n==1的情况容易处理：长×宽即可
3. n==2分两种情况
两个矩形分离
两个矩形有交集
需要注意的点：数据范围为10000*100000，要用long long 类型。
*/
#include <iostream>
#include <iomanip>
#include<stdio.h>
using namespace std;
typedef long long ll;
struct node{//左上角 和右下角
ll xa,ya,xb,yb;
}jx1,jx2,jx3;
int n;
node le_ri(){
node t;
cin>>t.xa>>t.ya>>t.xb>>t.yb;
if(t.xa>t.xb)swap(t.xa,t.xb);
if(t.ya>t.yb)swap(t.ya,t.yb);
return t;
}
ll s(node t){
return (t.xb-t.xa)*(t.yb-t.ya);
}
int main()
{
freopen("garden.in","r",stdin);
freopen("garden.out","w",stdout);
cin>>n;
jx1=le_ri();
if(n==1){
cout<<s(jx1)<<endl;
return 0;
}
jx2=le_ri();
if(jx1.xa>=jx2.xb||jx1.xb<=jx2.xa||jx1.ya>=jx2.yb||jx1.yb<=jx2.ya) {//2在1的左侧，右侧，下侧，上侧
cout<<s(jx1)+s(jx2)<<endl;
return 0;
}
//相交的情况
jx3.xa=max(jx1.xa,jx2.xa);
jx3.xb=min(jx1.xb,jx2.xb);
jx3.ya=max(jx1.ya,jx2.ya);
jx3.yb=min(jx1.yb,jx2.yb);
cout<<s(jx1)+s(jx2)-s(jx3)<<endl;
}
T4
/*
部分分1：考察数学与循环 50分
部分分2：N很大，循环超时，要优化。
N%i==0的情况下，i，N/i都是因子，找到小的，一定能对应到另一个大的。
小的最大多大呢？sqrt(N)
*/
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
int main()
{
freopen("gem.in","r",stdin) ;
freopen("gem.out","w",stdout);
LL N,M;scanf("%lld%lld",&N,&M);
LL ans=1;
for(LL i=1;i*i<=N;++i)if(N%i==0)
{
if(i<=M) ans=max(ans,i);
if(N/i<=M) ans=max(ans,N/i);
}
printf("%lld\n",N/ans);
return 0;
}T5
//数据范围小，本题考察递归、回溯。算法是深度优先搜索
#include <iostream>
using namespace std;
long long a[12],ans=0x7fffffffffffffff;
//初始化ans无限大
int n;
char ope[12];//记录操作字符
bool vis[12];//状态数组
void dfs(int cur) {
int i,j;
if(cur==n-1) { //回溯条件明确
for(i=0; i<n; i++) {
if(!vis[i])
ans=min(ans,a[i]);//没有被记录的数就是最终结果，求最小
}
return ;//回溯
}
for(i=0; i<n; i++) {
for(j=0; j<n; j++) {
if(i==j||vis[i]||vis[j]) continue;
//若为同一个数或已被选用，跳过
long long p=a[i];
vis[j]=1;
if(ope[cur]=='+')
a[i]+=a[j];
else if(ope[cur]=='*')
a[i]*=a[j];
dfs(cur+1);
vis[j]=0;
a[i]=p;//还原
}
}
}
int main() {
// cout<<(long long)850*957*975*935<<endl;
freopen("smallest.in","r",stdin);
freopen("smallest.out","w",stdout);
int i;
cin>>n;
for(i=0; i<n; i++) cin>>a[i];
for(i=0; i<n-1; i++) cin>>ope[i]; //输入
dfs(0);
cout<<ans;
return 0;
}
/*
7 17 3 25
+ * +
17+25=42
3*7=21
42+21=63
*/T6
/*本题考察宽度优先搜索。镜像处理起来比较麻烦
在搜索的过程中记录前驱，以便输出路径。
*/
#include <bits/stdc++.h>
using namespace std;
const int maxn = 25;
char s1[maxn][maxn], s2[maxn][maxn];
int vis[maxn][maxn][maxn][maxn];
array<int,4> pre[maxn][maxn][maxn][maxn];
char ans[maxn][maxn][maxn][maxn];
int step[maxn][maxn][maxn][maxn];
vector<char>rec;
queue<array<int,4>>q;
void down(int x, int y, int x_, int y_) {
int dx = x, dy = y, dx_ = x_, dy_ = y_;
if(s1[x + 1][y] == '.') dx++;
if(s2[x_ + 1][y_] == '.') dx_++;
if(!vis[dx][dy][dx_][dy_]) {
vis[dx][dy][dx_][dy_] = 1;
q.push({dx, dy, dx_, dy_});
pre[dx][dy][dx_][dy_] = {x, y, x_, y_};
ans[dx][dy][dx_][dy_] = 'D';
step[dx][dy][dx_][dy_] = step[x][y][x_][y_] + 1;
}
}
void left(int x, int y, int x_, int y_) {
int dx = x, dy = y, dx_ = x_, dy_ = y_;
if(s1[x][y - 1] == '.') dy--;
if(s2[x_][y_ + 1] == '.') dy_++;
if(!vis[dx][dy][dx_][dy_]) {
vis[dx][dy][dx_][dy_] = 1;
q.push({dx, dy, dx_, dy_});
pre[dx][dy][dx_][dy_] = {x, y, x_, y_};
ans[dx][dy][dx_][dy_] = 'L';
step[dx][dy][dx_][dy_] = step[x][y][x_][y_] + 1;
}
}
void right(int x, int y, int x_, int y_) {
int dx = x, dy = y, dx_ = x_, dy_ = y_;
if(s1[x][y + 1] == '.') dy++;
if(s2[x_][y_ - 1] == '.') dy_--;
if(!vis[dx][dy][dx_][dy_]) {
vis[dx][dy][dx_][dy_] = 1;
q.push({dx, dy, dx_, dy_});
pre[dx][dy][dx_][dy_] = {x, y, x_, y_};
ans[dx][dy][dx_][dy_] = 'R';
step[dx][dy][dx_][dy_] = step[x][y][x_][y_] + 1;
}
}
void up(int x, int y, int x_, int y_) {
int dx = x, dy = y, dx_ = x_, dy_ = y_;
if(s1[x - 1][y] == '.') dx--;
if(s2[x_ - 1][y_] == '.') dx_--;
if(!vis[dx][dy][dx_][dy_]) {
vis[dx][dy][dx_][dy_] = 1;
q.push({dx, dy, dx_, dy_});
pre[dx][dy][dx_][dy_] = {x, y, x_, y_};
ans[dx][dy][dx_][dy_] = 'U';
step[dx][dy][dx_][dy_] = step[x][y][x_][y_] + 1;
}
}
signed main() {
freopen("maze.in","r",stdin);
freopen("maze.out","w",stdout);
int qwq;
scanf("%d",&qwq);
for(int i = 1; i <= 20; i++) {
scanf("%s", s1[i] + 1);
scanf("%s", s2[i] + 1);
}
vis[20][20][20][1] = 1;
q.push({20, 20, 20, 1});
while(!q.empty()) {
array<int,4>u = q.front();
q.pop();
// if(step[u[0]][u[1]][u[2]][u[3]] > 26 && u[0] == 1 && u[2] == 1) cout << u[0] << ' ' << u[1] << ' ' << u[2] << ' ' << u[3] << ' ' << step[u[0]][u[1]][u[2]][u[3]] << "\n";
if(u[0] == 1 && u[1] == 20 && u[2] == 1 && u[3] == 1) {
break;
}
down(u[0], u[1], u[2], u[3]);
left(u[0], u[1], u[2], u[3]);
right(u[0], u[1], u[2], u[3]);
up(u[0], u[1], u[2], u[3]);
}
array<int,4> u = {1, 20, 1, 1};
array<int,4> st = {20, 20, 20, 1};
while(u != st) {
rec.push_back(ans[u[0]][u[1]][u[2]][u[3]]);
s1[u[0]][u[1]] = 'A';
s2[u[2]][u[3]] = 'A';
u = pre[u[0]][u[1]][u[2]][u[3]];
}
s1[20][20] = s2[20][1] = 'A';
cout << rec.size() << "\n";
if(qwq == 1) return 0;
reverse(rec.begin(), rec.end());
for(auto i : rec) cout << i;
puts("");
for(int i = 1; i <= 20; i++) {
cout << s1[i] + 1 << ' ' << s2[i] + 1 << '\n';
}
}