信息学奥赛-入门级 题库
数字游戏

#include<iostream>
#include<cstring>
using namespace std;
int main(){
char str[10];
cin >> str;
int ans=0;
for(int i=0;i<8;i++){//题意说了,长度固定是8
if(str[i]=='1'){
ans++;
}
}
cout << ans<<endl;
return 0;
}这道题考察字符串的操作、循环结构、分支结构等知识点。输入字符串,注意看题的最后,总长度是8.遍历字符串中每一个字符,如果字符为1则计数变量加一,最后输出计算变量的值。
公交换乘


#include <iostream>
#include <cmath>
#include <cstring>
using namespace std;
struct tra{
int kind,value,time;
}a[100005];
//保存打折车票的位置 车票的数量
int discount[100005],number;
int main()
{
int ans=0;
int n,start=1;
cin>>n;
//每张车票都要判断
for(int i=1;i<=n;i++){
cin>>a[i].kind>>a[i].value>>a[i].time ;
if(a[i].kind==0){//地铁票,需要花费
discount[++number]=i;
ans+=a[i].value;
}
else{
int j=0;
for(j=start;j<=number;j++){//超时的优惠票,没有用,舍弃
int t=discount[j];
if(a[i].time-a[t].time >45) {
start++;
continue;
}
if(a[i].value <=a[t].value){//未超时,且票据小于等于地铁票,可以用
a[t].value=0;
break;
}
}
if(j>number) {//没有优惠券
ans+=a[i].value;
}
}
}
//输出答案
cout<<ans<<endl;
return 0;
}和2016年海港有些像,模拟题。
车票有2中,如果是地铁票,必须要花钱。如果是公交车票,就不一定了。
如果45分钟内,有做过的地铁票,并且费用大于等于公交车的,就免费;
否则要花费。
纪念品


#include<iostream>
#include<cstring>
using namespace std;
int T,N,M;
int dp[10001];
int price[101][10001];
int main(){
cin>>T>>N>>M;
for(int i=1;i<=T;i++){
for(int j=1;j<=N;j++){
cin>>price[i][j];
}
}
int maxn=0;
for(int i=2;i<=T;i++){
maxn=0;
memset(dp,0,sizeof(dp));
for(int j=1;j<=N;j++){
for(int k=price[i-1][j];k<=M;k++){
dp[k]=max(dp[k],dp[k-price[i-1][j]]+price[i][j]-price[i-1][j]);
maxn=max(maxn,dp[k]);
}
}
M+=maxn;
}
cout <<M<< endl;
return 0;
}如果只有1天的话,买了再卖,总共剩下M个金币。
T天N种纪念币,根据题目设定范围,100以内,可以用二维表格推导。
时间不可逆,只能1~N。
每天买哪些纪念品呢?根据测试样例分析,纪念品任意多,没有个数限制。根据金币的上限,可以推到出这个就是完全背包。大家可以套一下完全背包的算法。每天需要做一次完全背包处理,当天不想卖出金币,相当于卖出金币再买入金币。
加工零件



#include<iostream>
#include<queue>
#include<cstring>
#include<cstdio>
using namespace std;
const int MAXN=1e5+5;
const int MAXM=2e5+5;
int n,m,que;
int head[MAXN],v[MAXM],next[MAXM],cnt=0;
int dis[MAXN][2];
void add_edge(int s,int t){
v[++cnt]=t;
next[cnt]=head[s];
head[s]=cnt;
}
void spfa(){
//0表示偶数
//1表示奇数
memset(dis,0x3f,sizeof(dis));
dis[1][0]=0;//起始路径0
queue<int> q;//队列实现
q.push(1);
while(!q.empty()){
int cur=q.front();
q.pop();
for(int i=head[cur];i;i=next[i]){
int np=v[i];
if(dis[cur][0]+1<dis[np][1] || dis[cur][1]+1<dis[np][0])
q.push(np);
dis[np][1]=min(dis[np][1],dis[cur][0]+1);
dis[np][0]=min(dis[np][0],dis[cur][1]+1);
}
}
}
int main(){
scanf("%d%d%d",&n,&m,&que);
for(int i=0;i<m;i++){
int u,v;
scanf("%d%d",&u,&v);
add_edge(u,v);
add_edge(v,u);
}
spfa();
while(que--){
int a,l;
scanf("%d%d",&a,&l);
if(head[1]&&dis[a][l&1]<=l)printf("Yes\n");
else printf("No\n");
}
return 0;
}这道题考察图论的知识运用,是属于最短路径的变形题目,可以利用spfa或Dijkstra来完成,难度较高。
根据性质,工人之间的关系是图。相连接,之间的路径权值是1。加工零件的过程可以相互传递,来回都是偶数次,因此在求个最短路时看奇偶步数内能否可达,要求与L的奇偶性一致。
乘方(pow)


#include <bits/stdc++.h>
using namespace std;
int main() {
long long ans, a, b;
ans = 1;
cin >> a >> b;
if (a == 1) { // 特判a=1,避免超时
cout << ans;
} else {
for (int i = 1; i <= b; ++i) {
ans *= a; // b个a相乘
if (ans > 1e9) { // 若乘积超过10^9,直接输出-1并终止程序
cout << -1;
return 0;
}
}
cout << ans; // 输出b个a相乘的结果
}
return 0;
}解密(decode)


#include<bits/stdc++.h>
using namespace std;
int k;
int main(){
scanf("%d",&k);
for(int i=1;i<=k;i++){
long long n,d,e;
scanf("%lld %lld %lld",&n,&d,&e);
long long s=n-d*e+2;
long long r=(n-d*e+2)/2,l=1;
while(l<r){
int mid=(l+r)/2;
if(mid*(s-mid)>=n){
r=mid;
}else{
l=mid+1;
}
}
if(l*(s-l)==n){
printf("%lld %lld\n",l,(s-l));
}else{
printf("NO\n");
}
}
return 0;
}逻辑表达式(expr)



//参考代码1
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;
inline void fio(string name)
{
freopen((name+".in").c_str(),"r",stdin);
freopen((name+".out").c_str(),"w",stdout);
}
inline long long read()
{
long long s=0,w=1,ch=getchar();
while(ch<'0'||ch>'9') ch=='-'?w=-1,ch=getchar():ch=getchar();
while(ch>='0'&&ch<='9') s=(s<<1)+(s<<3)+(ch^48),ch=getchar();
return s*w;
}
const int S=1000005;
int n;
char a[S];
int top,sta[S];
int rb[S],val[S];
int mlog[S],mn[S][25];
int cnt1,cnt2;
inline int que(int l,int r)
{
int k=mlog[r-l+1];
int x=mn[l][k],y=mn[r-(1<<k)+1][k];
return val[x]<val[y]?x:y;
}
int slove(int l,int r)
{
if(rb[l]==r) l++,r--;
if(l==r) return a[l]-'0';
int pos=que(l,r);
int lft=slove(l,pos-1);
if(lft==0&&a[pos]=='&')
{
cnt1++;
return 0;
}
if(lft==1&&a[pos]=='|')
{
cnt2++;
return 1;
}
int rig=slove(pos+1,r);
if(a[pos]=='&') return lft&rig;
else return lft|rig;
}
int main()
{
fio("expr");
scanf("%s",a+1);
n=strlen(a+1);
for(int i=1;i<=n;i++)
{
if(a[i]=='(') sta[++top]=i;
else if(a[i]==')') rb[sta[top--]]=i;
else if(a[i]!='0'&&a[i]!='1') val[i]=sta[top]*2+(a[i]=='&');
if(a[i]!='&'&&a[i]!='|') val[i]=1e8;
}
mlog[0]=-1;
for(int i=1;i<=n;i++) mlog[i]=mlog[i>>1]+1,mn[i][0]=i;
for(int j=1;j<=mlog[n];j++)
{
for(int i=1;i<=n-(1<<j)+1;i++)
{
int x=mn[i][j-1],y=mn[i+(1<<j-1)][j-1];
mn[i][j]=val[x]<val[y]?x:y;
}
}
printf("%d\n",slove(1,n));
printf("%d %d\n",cnt1,cnt2);
return 0;
}//参考代码2
#include<bits/stdc++.h>
#define N 3000005
using namespace std;
int n,m,top,ans1,ans2;
int to[N],to2[N],stk[N],cl[N],cr[N];
char str[N],s[N];
void build(int l,int r){
if(l==r) return;
if(str[l]=='('&&str[r]==')'&&to[l]==r){build(l+1,r-1);return;}
build(l,to[l]);
for(int i=to[l]+1;i<=r;i=to[i+1]+1){
build(i+1,to[i+1]);
if(str[i]=='&'){
cl[to2[i-1]]++;cr[to2[i+1]]++;
to2[to2[i+1]]=to2[i-1];
}
}
}
int solve(int l,int r){
if(l==r) return s[l]-'0';
if(s[l]=='('&&s[r]==')'&&to[l]==r) return solve(l+1,r-1);
int val=solve(l,to[l]);
for(int i=to[l]+1;i<=r;i=to[i+1]+1){
if(s[i]=='&'){
if(!val) ans1++;
else val&=solve(i+1,to[i+1]);
}else{
if(val) ans2++;
else val|=solve(i+1,to[i+1]);
}
}
return val;
}
signed main(){
freopen("expr.in","r",stdin);
freopen("expr.out","w",stdout);
scanf("%s",str+1);n=strlen(str+1);
for(int i=1;i<=n;i++){
if(str[i]=='0'||str[i]=='1') to[i]=i;
if(str[i]=='(') stk[++top]=i;
if(str[i]==')') to[stk[top]]=i,to[i]=stk[top],top--;
}
memcpy(to2,to,sizeof(to));
build(1,n);
for(int i=1;i<=n;i++){
while(cl[i]--) s[++m]='(';
s[++m]=str[i];
while(cr[i]--) s[++m]=')';
}
memset(to,0,sizeof(to));
top=0;
for(int i=1;i<=m;i++){
if(s[i]=='0'||s[i]=='1') to[i]=i;
if(s[i]=='(') stk[++top]=i;
if(s[i]==')') to[stk[top]]=i,to[i]=stk[top],top--;
}
printf("%d\n",solve(1,m));
printf("%d %d\n",ans1,ans2);
return 0;
}//参考代码3
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=1e6+5;
string s;
int sum,sun,to[N],stk[N],stkid,now;
char la;
stack<int>r[N/2];
int main()
{
freopen("expr.in","r",stdin);
freopen("expr.out","w",stdout);
cin>>s;
int n=s.size();
for(int i=n-1;i>=0;i--) s[i+1]=s[i];
for(int i=1;i<=n;i++) to[i]=i+1;
for(int i=1;i<=n;i++){
if(s[i]=='(') stk[++stkid]=i-1;
if(s[i]==')') to[stk[stkid--]]=i;
}
for(int i=1;i<=n;i++){
if(s[i]=='|'){
if(r[now].size()){
int TOP=r[now].top();
r[now].pop();
to[TOP]=i-1;
}
r[now].push(i);
}
if(s[i]=='(') now++;
if(s[i]==')'){
if(r[now].size()){
int TOP=r[now].top();
r[now].pop();
to[TOP]=i;
}
now--;
}
}
if(r[now].size()) to[r[now].top()]=n+1;
//for(int i=1;i<=n;i++) cout<<to[i]<<' ';cout<<endl;
for(int i=1;i<=n;i++){
if(s[i]=='('||s[i]==')') continue;
if(s[i]=='|'){
if(la=='1') {sun++;i=to[i];}
}
else if(s[i]=='&'){
if(la=='0') {sum++;i=to[i];}
}
else{
la=s[i];
}
}
cout<<la<<endl<<sum<<' '<<sun;
return 0;
}//参考代码4
#include<bits/stdc++.h>
#define REP(i,a,n) for(int i=(a);i<(int)(n);++i)
#define pb push_back
using namespace std;
string s;
int tp1,tp2;
int main(){
freopen("expr.in","r",stdin);
freopen("expr.out","w",stdout);
cin>>s;
int cnt1=0,cnt2=0,ans=0;
REP(i,0,s.size()){
if(s[i]=='1'||s[i]=='0')ans=s[i]-'0';
else if(s[i]=='&'){
if(ans==0){
++cnt1;
int res=0;
for(int j=i+1;j<(int)(s.size());++j){
if(s[j]=='(')++res;
else if(s[j]==')')--res;
if((!res)&&s[j]!='&'&&s[j]!='|'){
i=j;
break;
}
}
}
}else if(s[i]=='|'){
if(ans==1){
++cnt2;
int res=0;
for(int j=i+1;j<(int)(s.size());++j){
if(s[j]=='(')++res;
else if(s[j]==')')--res;
if(j!=(int)(s.size()-1)&&s[j+1]=='&')continue;
if((!res)&&s[j]!='&'&&s[j]!='|'){
i=j;
break;
}
}
}
}
}
cout<<ans<<endl;
cout<<cnt1<<' '<<cnt2<<endl;
return 0;
}分糖果

//参考代码1
#include <iostream>
using namespace std;
int n, l, r;
int main() {
cin >> n >> l >> r;
if (l / n == r / n) {
cout << r % n;
} else {
cout << n - 1;
}
return 0;
}//参考代码2
#include <iostream>
using namespace std;
int main() {
long long n, L, R;
cin >> n >> L >> R;
long long target = n - 1;
// 计算t的最小值(向上取整)
long long low = (L - target + n - 1) / n;
// 计算t的最大值(向下取整)
long long high = (R - target) / n;
if (low <= high) {
cout << target << endl;
} else {
cout << R % n << endl;
}
return 0;
}网络连接

#include <bits/stdc++.h>
using namespace std;
map<string, int> vis;
int n;
bool check(char s[]) {
int a = -1, b = -1, c = -1, d = -1, e = -1;
// 尝试读入,保存至变量中
int t = sscanf(s, "%d.%d.%d.%d:%d", &a, &b, &c, &d, &e);
// 必须读入5个部分才可能合法
if (t != 5) return 0;
// 检查各部分数值范围
if (a < 0 || a > 255) return 0;
if (b < 0 || b > 255) return 0;
if (c < 0 || c > 255) return 0;
if (d < 0 || d > 255) return 0;
if (e < 0 || e > 65535) return 0;
// 格式化后与原字符串对比,确保无冗余格式
char s2[35];
sprintf(s2, "%d.%d.%d.%d:%d", a, b, c, d, e);
int lens = strlen(s);
for (int i = 0; i < lens; i++) {
if (s[i] != s2[i]) {
return 0;
}
}
return 1;
}
int main() {
// freopen("network.in","r",stdin);
// freopen("network.out","w",stdout);
cin >> n;
for (int i = 1; i <= n; i++) {
char op[1005], ad[1005];
cin >> op >> ad;
string t(ad);
if (op[0] == 'S') { // 服务机操作
if (!check(ad)) {
cout << "ERR" << endl; // 地址不合法
} else if (vis.count(t) != 0) {
cout << "FAIL" << endl; // 已存在该服务机
} else {
cout << "OK" << endl; // 注册成功
vis[t] = i; // 记录编号
}
} else { // 客户机操作
if (!check(ad)) {
cout << "ERR" << endl; // 地址不合法
} else if (vis.count(t) == 0) {
cout << "FAIL" << endl; // 找不到对应服务机
} else {
cout << vis[ad] << endl; // 输出对应服务机编号
}
}
}
return 0;
}小熊的果篮

#include <bits/stdc++.h>
#define INF 200010
using namespace std;
int n;
set<int> s1, s2; // 存储两种下标的集合
int main() {
scanf("%d", &n);
s1.clear();
s2.clear();
int q;
for (int i = 1; i <= n; ++i) {
scanf("%d", &q);
if (q) {
s1.insert(i); // q为1时插入s1
} else {
s2.insert(i); // q为0时插入s2
}
}
// 插入INF防止set为空时操作出错
s1.insert(INF);
s2.insert(INF);
int nw = 0;
// p表示当前要操作的集合:0为s1,1为s2(选择最小下标的集合)
bool p = (*s1.begin() < *s2.begin()) ? 0 : 1;
// 循环处理,直到当前操作的集合只剩下INF(size > 1表示还有有效元素)
while ((!p && s1.size() > 1) || (p && s2.size() > 1)) {
if (!p) { // 处理s1
nw = *s1.upper_bound(nw); // 找nw之后的下一个元素
if (nw == INF) { // 已遍历完当前轮次,从头开始
nw = 0;
// 重新选择下一轮的起始集合
p = (*s1.begin() < *s2.begin()) ? 0 : 1;
puts("");
continue;
}
printf("%d ", nw); // 输出并从集合中删除
s1.erase(nw);
p = !p; // 切换到另一个集合
} else { // 处理s2(逻辑同上)
nw = *s2.upper_bound(nw);
if (nw == INF) {
nw = 0;
p = (*s1.begin() < *s2.begin()) ? 0 : 1;
puts("");
continue;
}
printf("%d ", nw);
s2.erase(nw);
p = !p;
}
}
puts(""); // 处理最后一个果篮的换行
// 输出剩余集合中的元素(每行一个)
while (s1.size() > 1) {
printf("%d\n", *s1.begin());
s1.erase(*s1.begin());
}
while (s2.size() > 1) {
printf("%d\n", *s2.begin());
s2.erase(*s2.begin());
}
return 0;
}优秀的拆分(power)

#include <bits/stdc++.h>
using namespace std;
/*
定义:分解为了若干个不同的 2 的正整数次幂
性质:是偶数,奇数不存在优秀的拆分
思路:
如果n是偶数,将n进行进制转换
10 -> 1010
*/
int a[110],n,k = 0;//k表示a数组的下标
int main(){
cin>>n;
//特判奇数的情况
if(n % 2 != 0){
cout<<-1;
return 0;
}
//进制转换
int t = 1;//表示2的次方
while(n != 0){
if(n % 2 != 0){
k++;
a[k] = t;
}
t = t * 2;
n = n / 2;
}
//逆序输出结果
for(int i = k;i >= 1;i--){
cout<<a[i]<<" ";
}
return 0;
}直播获奖( live)

#include <bits/stdc++.h>
using namespace std;
/*
1.获奖人数为k = max(1, int(p × w%))
2.选手的成绩均为不超过 600 的非负整数
思路:使用数组统计每个分值得分的人数
从大到小统计出k个人,最后一次循环对应的分值就是要求的获奖分数
*/
int a[610];
int n,w,x;
int main(){
scanf("%d%d",&n,&w);
int k;//获奖人数
int ans;//统计人数
//读入n个人的分数,读一个算一个
for(int i = 1;i <= n;i++){
scanf("%d",&x);
a[x]++;//统计每个分值对应的人数
//计算获奖人数
k = max(1,int(i * w / 100.0));
ans = 0;
//从最高分的人数向下统计出>=k个人
for(int j = 600;j >= 0;j--){
if(ans + a[j] < k) ans += a[j];//+=
else{
printf("%d ",j);
break;
}
}
}
return 0;
}表达式(expr)

#include <bits/stdc++.h>
using namespace std;
/*
取反某一个操作数的值时,原表达式的值为多少
思路:
1.读入表达式,将表达式建成二叉树
2.计算出表达式的值
3.深搜,求出哪些结点的值修改后对结果有影响
*/
const int N = 1e6 + 10;
struct node{
int to,next;
}a[N];//邻接表
int pre[N],k;//存储以每个点为起点的最后一条边的编号
int num[N];//存储二叉树每个结点的值
char c[N];//存储操作符
int m;//表示c数组的下标
bool f[N];//标记哪些点的值修改后对结果有影响
int n;
string s,w;//w用来存储每个操作数的下标
stack<int> st;//用于计算后缀表达式
//建边
void add(int u,int v){
k++;
a[k].to = v;
a[k].next = pre[u];
pre[u] = k;
}
//深搜求哪些结点的值修改后对结果有影响
void dfs(int x){
f[x] = true;
if(x <= n) return;//如果是叶子结点
if(c[x] == '!') dfs(a[pre[x]].to);
else{
int n1 = a[pre[x]].to,n2 = a[a[pre[x]].next].to;
if(c[x] == '&'){
if(num[n1] == 1) dfs(n2);
if(num[n2] == 1) dfs(n1);
}else if(c[x] == '|'){
if(num[n1] == 0) dfs(n2);
if(num[n2] == 0) dfs(n1);
}
}
}
int main()
{
getline(cin,s);
cin>>n;
for(int i = 1;i <= n;i++){
scanf("%d",&num[i]);
}
//分析表达式,建树
int x,y;
m = n;
for(int i = 0;i < s.size();i++){
if(isdigit(s[i])){
w = w + s[i];
//如果连续数字结束
if(i==s.size()-1||!isdigit(s[i+1])){
st.push(atoi(w.c_str()));//将操作数的下标入栈
w = "";
}
}else if(s[i] == '!'){
//如果是取反操作符
m++;
c[m] = s[i];//操作符的编号是m
x = st.top();//取栈顶元素来运算
st.pop(); //出栈
//建边
add(m,x);
num[m] = !num[x];
st.push(m);
}else if(s[i] == '&' || s[i] == '|'){
//如果是& |操作符
m++;
c[m] = s[i];
//取2个操作数
x = st.top();
st.pop();
y = st.top();
st.pop();
//建边
add(m,x);
add(m,y);
//计算结点的值
if(s[i] == '&') num[m] = num[x] & num[y];
else if(s[i] == '|') num[m] = num[x] | num[y];
st.push(m);
}
}
int ans = num[st.top()];
//cout<<ans;
//深搜求哪些结点的值修改后对结果有影响
dfs(st.top());//从根开始深搜
//q次询问
int q;
cin>>q;
while(q--){
scanf("%d",&x);
if(f[x]==true) printf("%d\n",!ans);
else printf("%d\n",ans);
}
return 0;
}方格取数(number)

#include <bits/stdc++.h>
using namespace std;
/*
左上角走到右下角
每一步只能向上、向下或向右走一格
不能重复经过已经走过的方格
计算的结果,要用long long
*/
const int N = 1010;
int a[N][N];//读入的每个点的值
typedef long long LL;
LL f[N][N];
int n,m;
int main(){
scanf("%d%d",&n,&m);
for(int i = 1;i <= n;i++){
for(int j = 1;j <= m;j++){
scanf("%d",&a[i][j]);
}
}
/*
DP求出走到每个点经过的数字和的最大值
一列一列求,对于每一列而言,要求从上向下走到每个点经过的数字和的最大值
也要求从下向上走到每个点经过的数字和的最大值
*/
memset(f,-0x7f,sizeof(f));
LL ma;//走到每个格子经过的数字和最大
f[1][0] = 0;
for(int j = 1;j <= m;j++){
//从上向下求
ma = -1e18;
for(int i = 1;i <= n;i++){
ma = max(ma,f[i][j-1]) + a[i][j];
f[i][j] = max(f[i][j],ma);
}
//从下向上求
ma = -1e18;
for(int i = n;i >= 1;i--){
ma = max(ma,f[i][j-1]) + a[i][j];
f[i][j] = max(f[i][j],ma);
}
}
cout<<f[n][m];
return 0;
}T1 扑克牌

#include <iostream>
#include <set>
using namespace std;
int main() {
int n;
cin >> n;
set<string> st;
while (n--) {
string s;
cin >> s;
st.insert(s);
}
cout << 52 - st.size() << endl;
return 0;
}题目给出已有的牌,要求计算最少需要补充多少张牌才能凑齐一副完整的扑克牌(52张)。给出的扑克牌可能包含重复的牌(即花色和点数都相同的牌),因此需要去重后计算缺失的牌数。
T2 地图探险

#include <iostream>
#include <cstring>
using namespace std;
const int N = 1e3 + 5;
int n, m, k, x, y, d, dir[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
char mp[N][N];
bool vis[N][N];
int main() {
int t;
cin >> t;
while (t--) {
memset(vis, false, sizeof (vis));
cin >> n >> m >> k >> x >> y >> d;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
cin >> mp[i][j];
vis[x][y] = true;
while (k--) {
int nx = x + dir[d][0], ny = y + dir[d][1];
if (!(nx >= 1 && nx <= n && ny >= 1 && ny <= m && mp[nx][ny] == '.')) {
d = (d + 1) % 4;
continue;
}
x = nx, y = ny;
vis[nx][ny] = true;
}
int ans = 0;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (vis[i][j] == true)
ans++;
}
}
cout << ans << endl;
}
return 0;
}需要的变量 / 数组
描述机器人状态需要的3个变量:
x:位置。
y:位置。
d:朝向(0~3)。
vis数组:
当机器人走过[x, y],vis[x][y] = true。
dir数组:
dir[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}}。
[x + dir[d][0], y + dir[d][1]]表示当机器人朝向为d时往前走一步之后的位置。
d = 0: 右 (0, 1)。
d = 1: 下 (1, 0)。
d = 2: 左 (0, -1)。
d = 3: 上 (-1, 0)。
核心思想
vis[x][y] = true;
while (k--) {
int nx = x + dir[d][0], ny = y + dir[d][1]; // 计算下一步的位置
if (!(nx >= 1 && nx <= n && ny >= 1 && ny <= m && mp[nx][ny] == '.')) { // 是否能走
d = (d + 1) % 4; // 若不能走 右转
continue;
}
x = nx, y = ny; // 若能走 更新
vis[nx][ny] = true;
}T3 小木棍

#include <iostream>
using namespace std;
string Solve(int n) {
if (n == 1)
return "-1";
if (n % 7 == 0)
return string(n / 7, '8');
if (n % 7 == 1)
return "10" + string((n - 8) / 7, '8');
if (n % 7 == 2)
return "1" + string((n - 2) / 7, '8');
if (n % 7 == 3)
return n == 3 ? "7" : n == 10 ? "22" : "200" + string((n - 17) / 7, '8');
if (n % 7 == 4)
return n == 4 ? "4" : "20" + string((n - 11) / 7, '8');
if (n % 7 == 5)
return "2" + string((n - 5) / 7, '8');
if (n % 7 == 6)
return "6" + string((n - 6) / 7, '8');
}
int main() {
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
cout << Solve(n) << endl;
}
return 0;
}拼出0~9分别需要的木棍数量:

求解思想:
因为拼出8所需的木棍最多(7根),所以用8,可以使位数更少
在保证位数最少的前提下,还要尽可能把高位的数字变小(必须保证位数最小)
按照思想,可以找到这样的规律:

T4 接龙

#include <iostream>
#include <vector>
using namespace std;
const int N = 1e5 + 5, R = 105;
vector<int> s[N];
int n, k, q;
vector<vector<int> > Solve(int mx) {
vector<vector<int> > dp(R, vector<int>(mx + 5, -1));
dp[0][1] = -2;
for (int r = 1; r <= 100; r++) {
for (int i = 1; i <= n; i++) {
int lst = -1;
for (int j = 0; j < s[i].size(); j++) {
int tmp = s[i][j];
if (lst != -1 && j - lst + 1 <= k) {
if (dp[r][tmp] == -1)
dp[r][tmp] = i;
else if (dp[r][tmp] != i)
dp[r][tmp] = -2;
}
if (dp[r - 1][tmp] != -1 && dp[r - 1][tmp] != i)
lst = j;
}
}
}
return dp;
}
int main() {
int t;
cin >> t;
while (t--) {
int mx = -1;
cin >> n >> k >> q;
for (int i = 1; i <= n; i++) {
int l;
cin >> l;
s[i].clear();
s[i].resize(l);
for (int j = 0; j < l; j++) {
cin >> s[i][j];
mx = max(mx, s[i][j]);
}
}
vector<vector<int> > dp = Solve(mx);
while (q--) {
int r, c;
cin >> r >> c;
cout << (dp[r][c] != -1 ? 1 : 0) << endl;
}
}
return 0;
}解题思路
本文的解题思想为dp。
dp[r][x]:接龙 r 轮、以 x 结尾的状态:
dp[r][x] = -1:不可实现。
dp[r][x] = i(一个自然数):可以通过词库 i 实现(最后一次接龙操作使用的是词库 i 中的某个连续子序列)。
dp[r][x] = -2:可以通过多个词库实现。
代码解析
完整的求解部分:
vector<vector<int> > Solve(int mx) {
vector<vector<int> > dp(R, vector<int>(mx + 5, -1));
dp[0][1] = -2;
for (int r = 1; r <= 100; r++) {
for (int i = 1; i <= n; i++) {
int lst = -1;
for (int j = 0; j < s[i].size(); j++) {
int tmp = s[i][j];
if (lst != -1 && j - lst + 1 <= k) {
if (dp[r][tmp] == -1)
dp[r][tmp] = i;
else if (dp[r][tmp] != i)
dp[r][tmp] = -2;
}
if (dp[r - 1][tmp] != -1 && dp[r - 1][tmp] != i)
lst = j;
}
}
}
return dp;
}逐行分析
mx:所有词库中的最大值,用于构建dp的第二个维度。
dp的大小为R(最大轮数) * mx(所有词库中的最大值)。
vector<vector<int> > Solve(int mx) {
vector<vector<int> > dp(R, vector<int>(mx + 5, -1));dp[0][1] = -2:作为虚拟起点,使得第一次接龙可以从数字 1 开始。
dp[0][1] = -2;
r:轮数。
i:尝试让第 i 个人接龙。
j:第 i 个人词库中第 j 个词语。
lst:当前序列 i 中最近一个满足接龙条件的起始位置(可以以lst为起点开始接龙)。
for (int r = 1; r <= 100; r++) {
for (int i = 1; i <= n; i++) {
int lst = -1;
for (int j = 0; j < s[i].size(); j++) {
}
}
}获取当前人员 i 的词库中第 j 个词语。
如果当前词库中有一个合适的起点可以开始接龙,并且长度合适:
那么选择子序列[lst, j]开始接龙。
更新当前状态。
如果上一轮接龙不是 i 在接龙,并且可以以tmp结束,那么这一轮也可以从tmp开始接龙。
int tmp = s[i][j];
if (lst != -1 && j - lst + 1 <= k) {
if (dp[r][tmp] == -1)
dp[r][tmp] = i; // 首次发现路径则记录序列i
else if (dp[r][tmp] != i)
dp[r][tmp] = -2; // 若已有其他序列可达则标记为多路径(-2)
}
if (dp[r - 1][tmp] != -1 && dp[r - 1][tmp] != i)
lst = j;小苹果(apple)
【题目描述】
小Y的桌子上放着n个苹果从左到右排成一列,编号为从1到n。
小苞是小Y的好朋友,每天她都会从中拿走一些苹果。
每天在拿的时候,小苞都是从左侧第1个苹果开始、每隔2个苹果拿走1个苹果。随后小苞会将剩下的苹果按原先的顺序重新排成一列。
小苞想知道,多少天能拿完所有的苹果,而编号为n的苹果是在第几天被拿走的?
【输入格式】
从文件apple.in中读入数据。
输入的第一行包含一个正整数n,表示苹果的总数。
【输出格式】
输出到文件apple.out中。
输出一行包含两个正整数,两个整数之间由一个空格隔开,分别表示小苞拿走所有苹果所需的天数以及拿走编号为n的苹果是在第几天。
【样例1输入】
【样例1输出】
【样例1解释】
小苞的桌上一共放了8个苹果。
小苞第一天拿走了编号为1、4、7的苹果。
小苞第二天拿走了编号为2、6的苹果。
小苞第三天拿走了编号为3的苹果。
小苞第四天拿走了编号为5的苹果。
小苞第五天拿走了编号为8的苹果。
【样例2】
见选手目录下的apple/apple2.in与apple/apple2.ans。


