HGOI11.5集训题解
题解
今天居然死在了大模拟上面orz我不是一个好的码农
第一题——数独(sudoku)
【题目描述】
(题目太长,直接截图)
- 这个实力考模拟,但是merge的题面我最后五分钟才看懂。字符串读入读错orz,实力爆零。
- 就模拟吧,数组随便开就过了orz。考细心
#include <bits/stdc++.h>
using namespace std;
void fff(){
freopen("sudoku.in","r",stdin);
freopen("sudoku.out","w",stdout);
}
const int MAXN=110;
const int N=11;
int mm[11][11]={
0,0,0,0,0,0,0,0,0,0,0,
0,1,1,1,2,2,2,3,3,3,0,
0,1,1,1,2,2,2,3,3,3,0,
0,1,1,1,2,2,2,3,3,3,0,
0,4,4,4,5,5,5,6,6,6,0,
0,4,4,4,5,5,5,6,6,6,0,
0,4,4,4,5,5,5,6,6,6,0,
0,7,7,7,8,8,8,9,9,9,0,
0,7,7,7,8,8,8,9,9,9,0,
0,7,7,7,8,8,8,9,9,9,0,
0,0,0,0,0,0,0,0,0,0,0
};
inline int read(){
char ch=getchar();int x=0;
while(ch<'0'||ch>'9') ch=getchar();
while(ch>='0'&&ch<='9') x=(x<<1)+(x<<3)+ch-'0',ch=getchar();
return x;
}
int mp[MAXN][N][N];
bool row[MAXN][N][N],column[MAXN][N][N],square[MAXN][N][N];
char ch[25],chr[10];
int get_block(int x,int y){return mm[x][y];}
void Insert(int num,int x,int y,int k){
if(mp[num][x][y]!=0){printf("Error!\n");return;}
if(row[num][x][k]){printf("Error:row!\n");return;}
if(column[num][y][k]){printf("Error:column!\n");return;}
if(square[num][get_block(x,y)][k]){printf("Error:square!\n");return;}
printf("OK!\n");
mp[num][x][y]=k;
row[num][x][k]=true;
column[num][y][k]=true;
square[num][get_block(x,y)][k]=true;
}
void Delete(int num,int x,int y){
if(mp[num][x][y]==0){printf("Error!\n");return;}
printf("OK!\n");
int k=mp[num][x][y];
mp[num][x][y]=0;
row[num][x][k]=false;
column[num][y][k]=false;
square[num][get_block(x,y)][k]=false;
}
int temp[11];
void Query(int num,int x,int y){
if(mp[num][x][y]!=0){printf("Error!\n");return;}
int tempn=0;
for(int i=1;i<=9;i++){
if(row[num][x][i]||column[num][y][i]||square[num][get_block(x,y)][i]) continue;
temp[++tempn]=i;
}
printf("%d\n",tempn);
for(int i=1;i<=tempn;i++) printf("%d\n",temp[i]);
}
void Merge(int num,int num1,int num2){
int cnt1=0,cnt2=0;
memset(mp[num],0,sizeof(mp[num]));
memset(row[num],false,sizeof(row[num]));
memset(column[num],false,sizeof(column[num]));
memset(square[num],false,sizeof(square[num]));
for(int i=1;i<=9;i++){
for(int j=1;j<=9;j++){
int val1=mp[num1][i][j],val2=mp[num2][i][j];
if(!(row[num][i][val1]||column[num][j][val1]||square[num][get_block(i,j)][val1])&&val1!=0){
mp[num][i][j]=val1;
row[num][i][val1]=true;
column[num][j][val1]=true;
square[num][get_block(i,j)][val1]=true;
cnt1++;
continue;
}
if(!(row[num][i][val2]||column[num][j][val2]||square[num][get_block(i,j)][val2])&&val2!=0){
mp[num][i][j]=val2;
row[num][i][val2]=true;
column[num][j][val2]=true;
square[num][get_block(i,j)][val2]=true;
cnt2++;
continue;
}
}
}
printf("%d %d\n",cnt1,cnt2);
}
void Print(int num){
for(int i=1;i<=9;i++){
printf("+-+-+-+-+-+-+-+-+-+\n");
for(int j=1;j<=9;j++){
printf("|%d",mp[num][i][j]);
}
printf("|\n");
}
printf("+-+-+-+-+-+-+-+-+-+\n");
}
int main(){
// fff();
for(int i=1;i<=19;i++){
scanf("%s",ch);
if(i%2==1) continue;
for(int j=1;j<19;j+=2){
int x=i/2,y=j/2+1;
mp[0][x][y]=ch[j]-'0';
row[0][x][ch[j]-'0']=true;
column[0][y][ch[j]-'0']=true;
square[0][get_block(x,y)][ch[j]-'0']=true;
}
}
int T;T=read();
for(int i=1;i<=T;i++){
for(int k=1;k<=9;k++)
for(int j=1;j<=9;j++){
mp[i][k][j]=mp[i-1][k][j];
row[i][k][j]=row[i-1][k][j];
column[i][k][j]=column[i-1][k][j];
square[i][k][j]=square[i-1][k][j];
}
cin>>chr;
if(chr[0]=='I'){int x,y,k;x=read(),y=read(),k=read();Insert(i,x,y,k);continue;}
if(chr[0]=='D'){int x,y;x=read(),y=read();Delete(i,x,y);continue;}
if(chr[0]=='Q'){int x,y;x=read(),y=read();
Query(i,x,y);continue;}
if(chr[0]=='M'){int x,y;x=read(),y=read();Merge(i,x,y);continue;}
if(chr[0]=='P'){Print(i);continue;}
}
}
第二题——最大序列(seq)
【题目描述】
- 给出入栈序列,求出字典序最大的出站序列
- 这个由于要字典序最大,就先找到字典序最大的数值,之前的全部进栈,然后看栈顶和当前这个元素之后的最大的元素进行比较,如果栈顶大就输出栈顶,否则继续找之后最大的元素,以此类推。
#include <bits/stdc++.h>
using namespace std;
void fff(){
freopen("seq.in","r",stdin);
freopen("seq.out","w",stdout);
}
inline int read(){
char ch=getchar();int x=0;
while(ch<'0'||ch>'9') ch=getchar();
while(ch>='0'&&ch<='9') x=(x<<1)+(x<<3)+ch-'0',ch=getchar();
return x;
}
const int N=2e5+10;
int n;
int a[N],m[N];
int sta[N],top=0;
int maxx(int x,int y){return a[x]>a[y]?x:y;}
int query(int l){return m[l];}
int main(){
// fff();
n=read();
for(int i=1;i<=n;i++)
a[i]=read();
m[n]=n;
for(int i=n-1;i>=1;i--){
m[i]=maxx(i,m[i+1]);
}
int pos=0;
for(int i=1;i<=n;i++){
int tar=query(pos+1);
if(pos==n){
printf("%d ",a[sta[top--]]);
continue;
}
if(top==0){
while(pos<tar){
sta[++top]=(++pos);
}
printf("%d ",a[sta[top--]]);
}else{
int val=a[sta[top]];
if(val>a[tar]){
printf("%d ",a[sta[top--]]);
continue;
}else{
while(pos<tar){
sta[++top]=(++pos);
}
printf("%d ",a[sta[top--]]);
}
}
}
}
第三题——思考熊的马拉松(running)
【题目描述】
- 给出n个人的速度,要求跑L圈,每圈A米,所有人从同一起点出发,要求求出在比赛结束之前出现多少圈套圈(比赛时间为第一个人跑完所有圈的时间)
-
先将所有人的速度进行从小到大排序
-
这个其实比较容易列出式子
-
化简之后就变成
-
然后考虑下取整,将整除提出:
-
剩下的一部分显然和下取整差的最多为1,考虑对于对那么只需要知道对于单个的j之前有多少个取模之后的比他余数小的有多少就可以了
#include <bits/stdc++.h>
#define LL long long
#define LD long double
using namespace std;
void fff(){
freopen("running.in","r",stdin);
freopen("running.out","w",stdout);
}
inline LL read(){
char ch=getchar();LL x=0;
while(ch<'0'||ch>'9') ch=getchar();
while(ch>='0'&&ch<='9') x=(x<<1)+(x<<3)+ch-'0',ch=getchar();
return x;
}
const int N=1e5+10;
int n,A,L;
LL a[N],sum[N],c[N];
inline int lowbit(int x){return x & (-x);}
void insert(int x){for(int i=x;i<=n;i+=lowbit(i)) c[i]++;}
int getsum(int x){int res=0;for(int i=x;i;i-=lowbit(i))res+=c[i];return res;}
LL b[N];
int main(){
// fff();
int T,C;T=read(),C=read();
if(C<11){
while(T--){
n=read(),A=read(),L=read();
for(int i=1;i<=n;i++) a[i]=read();
sort(a+1,a+n+1);
LL ans=0;
for(int i=2;i<=n;i++){
for(int j=1;j<i;j++){
ans+=(LL)((LD)L*(a[i]-a[j])/a[n]);
}
}
printf("%lld\n",ans);
}
}else if(C<15){
while(T--){
n=read(),A=read(),L=read();
for(int i=1;i<=n;i++) a[i]=read();
sort(a+1,a+n+1);
sum[0]=0;
LL tt=L/a[n],ans=0;
for(int i=1;i<=n;i++)sum[i]=sum[i-1]+a[i];
for(int i=2;i<=n;i++){
ans+=(a[i]*(i-1)-sum[i-1]);
}
ans*=tt;
printf("%lld\n",(LL)ans);
}
}else{
while (T--) {
scanf("%d%lld%lld", &n, &A, &L);
LL ans = 0;
LL maxv = 0;
for (int i = 1; i <= n; i++) {
c[i] = 0;
scanf("%lld", &a[i]);
maxv = max(maxv, a[i]);
a[i] *= L;
}
sort(a + 1, a + n + 1);
reverse(a + 1, a + n + 1);
for (int i = 1; i <= n; i++) {
ans += (a[i] / maxv) * (LL) (n - 2 * i + 1);
a[i] %= maxv;
}
for (int i = 1; i <= n; i++) b[i] = a[i];
sort(b + 1, b + n + 1);
int m = int(unique(b + 1, b + n + 1) - (b + 1));
for (int i = 1; i <= n; i++) {
a[i] = int(lower_bound(b + 1, b + m + 1, a[i]) - b);
ans -= getsum(a[i] - 1);
insert(a[i]);
}
printf("%lld\n", ans);
}
}
}