先刷前四题，剩下的有空补。
题意：给出x 轴上的n 个点，问两个点之间的最短距离是多少，有多少个最短距离。
思路：排序后遍历。
代码：
#include<stdio.h>
#include<algorithm>
using namespace std;
#define N 200005
int w[N];
int main(){
int n;
while(~scanf("%d", &n)){
for(int i=; i<n; i++){
scanf("%d", &w[i]);
}
sort(w, w+n);
int mint=w[]-w[], co=;
for(int i=; i<n; i++){
if(w[i]-w[i-]<mint){
mint=w[i]-w[i-];
co=;
}
else if(w[i]-w[i-]==mint) co++;
}
printf("%d %d\n", mint, co);
}
return ;
}
792A AC代码
题意：1-n n个数围成一圈，初始位置为1，有m 个操作，每个操作给一个整数x，表示前进x 步后删去当前位置的数，再前进一步，输出每次操作删除的数
思路：模拟，用pos表示当前位置，循环m 次。注意得到x 后先取余当前剩余数量。
代码：
#include<stdio.h>
int main(){
int n, m, x;
while(~scanf("%d%d", &n, &m)){
bool vis[]={}, flag=false;
int pos=, num=n;
while(m--){
scanf("%d", &x);
x=x%num;
while(x--){
do
{
pos++;
pos%=n;
}while(vis[pos]==);
}
if(flag) printf(" ");
flag=true;
printf("%d", pos+);
vis[pos]=;
do
{
pos++;
pos%=n;
}while(vis[pos]==);
num--;
}
printf("\n");
}
return ;
}
792B AC代码
题意：给一个数，问最少删除多少位后可以被3 整除。
思路：
有一个大数取余要先理解。用sum 保存所有位和取余3 的结果。
如果sum==0，不需要删除；
如果sum==1，有可能删除一位1（取余后），有可能删除两位2；
如果sum==2，有可能删除一位2，有可能删除两位1。
写一个函数del（char *s, int k）表示从s 里删除一个数字k 并且去除前导0。接着几个if、else判断一下就可以了。
代码：
#include<stdio.h>
#include<string.h>
void del(char *s, int k){
int ls=strlen(s), i;
for(i=ls-; i>=; i--){
if((s[i]-'')%==k) break;
}
if(i==-) return ;
for(int j=i; j<ls; j++) s[j]=s[j+];
if(s[]==){
s[]='-';
s[]='';
s[]=;
return ;
}
for(i=; s[i]; i++){
if(s[i]!='') break;
}
if(s[i]==) s[]='', s[]=;
else{
for(int j=i; j<ls; j++){
s[j-i]=s[j];
}
}
}
char s[], ts[];
int main(){
while(~scanf("%s", s)){
int sum=;
for(int i=; s[i]; i++){
sum+=s[i]-'';
sum%=;
}
if(sum==) printf("%s\n", s);
else{
int n1=, n2=;
for(int i=; s[i]; i++){
if((s[i]-'')%==) n1++;
else if((s[i]-'')%==) n2++;
}
if(sum==){
if(n2<){
del(s, );
printf("%s\n", s);
}
else if(n1==){
del(s, );
del(s, );
printf("%s\n", s);
}
else{
strcpy(ts, s);
int ls1, ls2;
del(ts, );
ls1=strlen(ts);
del(s, );
del(s, );
ls2=strlen(s);
if(ls1>ls2) printf("%s\n", ts);
else printf("%s\n", s);
}
}
else{
if(n2==){
del(s, );
del(s, );
printf("%s\n", s);
}
else if(n1<){
del(s, );
printf("%s\n", s);
}
else{
strcpy(ts, s);
int ls1, ls2;
del(ts, );
del(ts, );
ls1=strlen(ts);
del(s, );
ls2=strlen(s);
if(ls1>ls2) printf("%s\n", ts);
else printf("%s\n", s);
}
}
}
}
return ;
}
792C AC代码
792D Paths in a Complete Binary Tree
题意：给一个n ，一个m ，n 表示有n 个结点的完整二叉树，m 表示m 个询问，每次询问给出初始结点编号和移动序列，问移动后的结点编号。（树结点编码依据中序遍历）
思路：
预处理+模拟。
可以先通过一个dfs找到初始位置的层数，这个dfs里面同时求出初始位置到根的路径（用于判断当前位置是父结点的左孩子或右孩子）。
接着根据初始位置的层数，先预处理一下移动序列，把不合理的操作去掉。（简化后续操作难度）
接着模拟当前位置变化即可。分三种情况处理即可（重点的子树结点数量可以通过当前层数求出）
代码：
#include<stdio.h>
#define LL long long int getNum(LL n){
int ret=;
while(n){
n>>=;
ret++;
}
return ret;
} int dfs(LL l, LL r, LL p, bool *ss, int &ssp, int ceng){ // 确定初始位置的行
LL mid=(l+r)/;
if(mid==p) return ceng;
else if(mid>p){
ss[ceng]=;
ssp=ceng;
return dfs(l, mid-, p, ss, ssp, ceng+);
}
else{
ss[ceng]=;
ssp=ceng;
return dfs(mid+, r, p, ss, ssp, ceng+);
}
} void init(char *s, int rp, int num){
int j=;
for(int i=; s[i]; i++){
if(s[i]=='L' || s[i]=='R'){
if(rp==num);
else{
rp++;
s[j++]=s[i];
}
}
else{
if(rp==);
else{
rp--;
s[j++]=s[i];
}
}
}
s[j]=;
} LL dp[];
LL solve(char *s, bool *ss, int ssp, LL p, int rp, int num){
if(s[]==) return p;
if(s[]=='L'){
LL ln=dp[num-rp]-;
p=p-ln+(ln-)/;
rp++;
ss[++ssp]=;
}
else if(s[]=='R'){
LL rn=dp[num-rp]-;
p=p++(rn-)/;
rp++;
ss[++ssp]=;
}
else{
if(ss[ssp]==){
LL rn=dp[num-rp]-;
p=p++rn;
}
else{
LL ln=dp[num-rp]-;
p=p--ln;
}
ssp--;
rp--;
} return solve(s+, ss, ssp, p, rp, num);
} char s[];
bool ss[];
int main(){
dp[]=;
for(int i=; dp[i-]<=1e18; i++){
dp[i]=dp[i-]*;
}
LL n, p;
int m;
while(~scanf("%I64d%d", &n, &m)){
int num = getNum(n);
while(m--){
scanf("%I64d%s", &p, s);
int ssp=;
int rp = dfs(, n, p, ss, ssp, );
init(s, rp, num); printf("%I64d\n", solve(s, ss, ssp, p, rp, num));
}
}
return ;
}
792D AC代码