# Code
:::spoiler mouse_maze
```c=
#include <stdio.h>
char maze[505][505];
int R, C;
int startRow, startCol,end_i,end_j,gx[4]={1,0,-1,0},gy[4]={0,1,0,-1},sstep[505][505];
void pathfinding(int row, int col,int step){
for(int i=0;i<4;i++){
int xx=row+gx[i],yy=col+gy[i];
if(xx>=0&&yy>=0&&xx<R&&yy<C&&(maze[xx][yy]!='#')&&(sstep[xx][yy]==0||sstep[xx][yy]>step+1)){
sstep[xx][yy]=step+1;
pathfinding(xx,yy,step+1);
}
}
}
int main(){
int N;
scanf("%d", &N);
for(int i=0;i<N;i++){
scanf("%d %d", &R, &C);
for(int j=0;j<R;j++) scanf("%s", maze[j]);
for(int i=0;i<500;i++) for(int j=0;j<500;j++) sstep[i][j]=0;
for(int j=0;j<R;j++) for(int k=0;k<C;k++){
if(maze[j][k]=='S') startRow = j,startCol = k;
if(maze[j][k]=='F') end_i=j,end_j=k;
}
sstep[startRow][startCol]=1;
pathfinding(startRow, startCol,1);
printf("%d\n",sstep[end_i][end_j]-1);
}
}
```
:::
:::spoiler 11711
```c=
#include<stdlib.h>
unsigned*** new_3d_array(unsigned n,unsigned m,unsigned k);
void delete_3d_array(unsigned ***arr);
unsigned*** new_3d_array(unsigned n,unsigned m,unsigned k){
unsigned*** arr;
unsigned** pptr;
unsigned* ptr;
//allocate the memory needed all at once.
arr = (unsigned***)malloc(n*sizeof(unsigned**) + n*m*sizeof(unsigned*)\
+ n*m*k*sizeof(unsigned));
//Note that since this is an array, bytes of the same types should be put in the same sections.
//double pointer to the first pointer element of arr. (&arr[0][0])
pptr = (unsigned**)(arr+n);
//pointer to the first unsigned element of arr. (&arr[0][0][0])
ptr = (unsigned*)(arr+n+n*m);
for(unsigned i=0;i<n;i++){
//use pptr to make arr[i] point to correct spots.
//Note that arr[i] points to an array of pointers (arr[i][0~m-1])
arr[i] = pptr + m*i;
for(unsigned j=0;j<m;j++){
//use ptr to make arr[i][j] point to correct spots.
//Note that arr[i][j] points to an array of unsigned bytes (arr[i][j][0~k-1])
arr[i][j] = ptr + m*k*i + k*j;
}
}
return arr;
}
void delete_3d_array(unsigned ***arr){
//one malloc -> one free
free(arr);
}
/*
arr=(unsigned***)malloc(n*m*k*sizeof(unsigned));
pttr=(unsigned**)malloc(n*m*sizeof(unsigned*));
ptr=(unsigned*)malloc(n*sizeof(unsigned**));
*/
```
:::
:::spoiler 12490
```c=
#ifndef FUNCTION_H
#define FUNCTION_H
#include<string.h>
int solver(int **ptr, int *sum, char *s){
int len=strlen(s),num=0,ok=0,f=1,n=0;
for(int i=0;i<=len;i++){
if(s[i]>='0'&&s[i]<='9') num=num*10+s[i]-'0',ok=1;
else{
if(ok) *ptr[n]=f*num,*sum+=f*num,n++;
if(s[i]=='-') f=-1;
else f=1;
ok=0;num=0;
}
}
return n;
}
#endif
```
:::
## 第二次期中小抄
String Split
:::spoiler 解法一
```c=
#include <string.h>
#include <stdlib.h>
char **split_str_by_pattern(char* str, char* pattern, int* split_num){
int len1=strlen(str),len2=strlen(pattern);
char **arr=(char**)malloc((len1/2+1)*sizeof(char*));
int idx=0,i=0,tmp=0;
while(i<len1){
if(i+len2>=len1){
if(strcmp(&str[i],pattern)==0) break;
arr[idx]=(char*)malloc((i-tmp+2)*sizeof(char));
strcpy(&arr[idx][0],&str[tmp]);
idx++; break;
}
char temp=str[i+len2];
str[i+len2]='\0';
if(strcmp(&str[i],pattern)==0){
if(i!=tmp){
char temp2=str[i]; str[i]='\0';
arr[idx]=(char*)malloc((i-tmp+2)*sizeof(char));
strcpy(&arr[idx][0],&str[tmp]);
idx++;str[i]=temp2;
}
str[i+len2]=temp, i+=len2, tmp=i;
}
else str[i+len2]=temp,i++;
}
*split_num=idx;
return arr;
}
void free_result(char **result, int split_num){
for(int i=0;i<split_num;i++) free(result[i]);
free(result);
}
```
:::
---
:::spoiler 解法二
```c=
char **split_str_by_pattern(char *str, char *pattern, int *split_num){
int str_len = strlen(str),pat_len = strlen(pattern);
char **res = (char **)malloc(500*sizeof(char *)+500*500*sizeof(char));
char *entry = (char *)(res+500);
for (int i = 0; i < 500; i++) res[i]=entry+(i * 500);
int s=0, e=0, find_pattern, split_idx=0;
for (int i=0;i<str_len;){
find_pattern=strncmp(str+i,pattern,pat_len);
if (find_pattern==0){
if (s!=e){
strncpy(res[split_idx],str+s,e-s);
res[split_idx][e - s]='\0',split_idx++;
}
i+=pat_len, s=i,e=i;
}
else i++, e=i;
}
if (s!=e) strncpy(res[split_idx], str+s, e-s);
split_idx++;
*split_num = split_idx;
return res;
}
void free_result(char **result, int split_num){ free(result);}
```
:::
---
Secrecy between Bob and Alice
:::spoiler Swap
```c=
#include <stdio.h>
#include <string.h>
#define swap(a, b) (a ^= b ^= a ^= b)
char p[5005],t[5005][5005],ch[30];
int ans[5005], wh[5005];
int main(){
int n; scanf("%d %s", &n, p);
int sz = 0, len = strlen(p);
for(int i = 0; i < n; i++) scanf("%s", t[i]);
for(int i = 0; i < n; i++){
for(int j = 0; j < 26; j++) ch[j] = '#';
int is = 0;
for(int j = 0; j < sz; j++){
if(strcmp(t[i], t[wh[j]]) == 0){
ans[j]++,is = 1;
break;
}
}
if(is) continue;
if(strlen(t[i]) != len) continue;
for(int j = 0; j < len; j++){
if(ch[t[i][j] - 'a'] != '#') {
if(ch[t[i][j] - 'a'] != p[j]){
is = 1; break;
}} else{ch[t[i][j] - 'a'] = p[j];}
}
for(int j = 0; j < 26; j++) for(int k = 0; k < j; k++)
if(ch[j] == ch[k] && ch[j] != '#')is = 1;
if(is) continue;
ans[sz] = 1, wh[sz] = i, sz++;
}
for(int i = sz - 1; i >= 0; i--){
for(int j = 0; j < i; j++){
if(ans[j] < ans[j + 1]){
swap(ans[j], ans[j+1]);
swap(wh[j], wh[j + 1]);
}else if(ans[j] == ans[j + 1]) if(strcmp(t[wh[j]], t[wh[j + 1]]) > 0)
swap(wh[j], wh[j + 1]);
}
}
printf("%d\n", sz);
for(int i = 0; i < sz; i++) printf("%s %d\n", t[wh[i]], ans[i]);
return 0;
}
```
:::
---
Bouncing ball
:::spoiler 水題
```c=
#include<stdio.h>
#include<math.h>
int main(){
int t;long long bound[3],position[3],velocity[3],N;
scanf("%d",&t);
while(t--){
for(int i=0;i<3;i++) scanf("%lld",&bound[i]);
for(int i=0;i<3;i++) scanf("%lld",&position[i]);
for(int i=0;i<3;i++) scanf("%lld",&velocity[i]);
scanf("%lld",&N);
for(int i=0;i<3;i++){
position[i]=(velocity[i]*N)%(2*bound[i])+position[i];
while(position[i]>bound[i]||position[i]<0){
if(position[i]<0) position[i]=-position[i];
else position[i]=bound[i]-(position[i]-bound[i]);
}
}
printf("%lld %lld %lld\n",position[0],position[1],position[2]);
}
}
```
:::
---
Writing app
:::spoiler DP
```c=
#include<stdio.h>
#define max(x,y) (x>y?x:y)
int ar[1005][1005]; char arr[1005];
int dp(int l,int r){
if(l>r) return 0;
if(l==r) return 1;
if(ar[l][r]!=0) return ar[l][r];
if(arr[l]==arr[r]) return ar[l][r]=dp(l+1,r-1)+2;
return ar[l][r]=max(dp(l+1,r),dp(l,r-1));
}
int main(){
int n=0,m=0;
scanf("%d %d %s",&n,&m,arr);
for(int i=0;i<1005;i++) for(int j=0;j<1005;j++) ar[i][j]=0;
if(m>=n-dp(0,n-1)) printf("Yes\n");
else printf("No\n");
}
```
:::
---
Character Replacement
:::spoiler 水題
```c=
int changeCharacter(char *str, char a, char b){
int sstr=strlen(str);
for(int i=0;i<=sstr;i++){
if(str[i]==a) str[i]=b;
}
return 0;
}
```
:::
---
Hack's script
:::spoiler 遞迴
```c=
#include<stdio.h>
#include<string.h>
char a1[25],a2[25];int str1,str2,newone[25],check=0;
void find(int idx,int idy){
int i,j;
if(idx==str1&&idy==str2){
int done=0;
for(i=0,j=0;i<idy;i++){
if(newone[j]==-1){j++;continue;}
if(done) printf(" ");
while(j<str1&&newone[j]==i) printf("%c",a1[j]),done=1,j++;
}
printf("\n"),check=1;
}
else if(idx<str1&&idy<str2){
if(a2[idy]=='#'){
newone[idx]=idy;
find(idx+1,idy+1);
find(idx+1,idy);}
else{
newone[idx]=-1;
if(a1[idx]==a2[idy]) find(idx+1,idy+1);
}
}
}
int main(){
scanf("%s %s",a1,a2);
str1=strlen(a1),str2=strlen(a2);
find(0,0);
if(!check) printf("What the hack!?\n");
}
```
:::
---
Powerful script
:::spoiler 加$
```c=
#include<stdio.h>
#include<string.h>
char a1[25],a2[25];int str1,str2,newone[25],check;
void find(int idx,int idy){
int i,j;
if(idx==str1&&idy==str2){
for(i=0,j=0;i<idy;i++)
if(newone[j]==-1) {
j++;
continue;
}
check++;
}
else if(idx<str1&&idy<str2){
if(a2[idy]=='#'){
newone[idx]=idy;
find(idx+1,idy+1);
find(idx+1,idy);
}
else if(a2[idy]=='$'){
newone[idx]=idy;
find(idx+1,idy+1);
if(a1[idx+1]==a1[idx]) find(idx+1,idy);
}
else{
newone[idx]=-1;
if(a1[idx]==a2[idy]) find(idx+1,idy+1);
}
}
}
int main(){
int t;
scanf("%d",&t);
while(t--){
scanf("%s %s",a1,a2);
check=0;
str1=strlen(a1),str2=strlen(a2);
find(0,0);
printf("%d\n",check);
}
}
```
:::
---
Hakka's Maze
:::spoiler DFS
```c=
#include<stdio.h>
char a[1005][1005];
int is[1005][1005];
int gx[4]={1,-1,0,0},gy[4]={0,0,1,-1};
int n,m;
void dfs(int idx,int idy){
is[idx][idy]=1;
for(int i=0;i<4;i++){
int xx=idx+gx[i],yy=idy+gy[i];
if(xx>=0&&yy>=0&&xx<n&&yy<m&&!is[xx][yy]&&a[xx][yy]!='#') dfs(xx,yy);
}
}
int main(){
int t;scanf("%d",&t);
while(t--){
scanf("%d %d",&n,&m);
for(int i=0;i<n;i++) scanf("%s",a[i]);
for(int i=0;i<n;i++) for(int j=0;j<m;j++) is[i][j]=0;
dfs(0,0);
int flag=0;
for(int i=0;i<n;i++) for(int j=0;j<m;j++){
flag=flag||(a[i][j]=='T'&&is[i][j]);
}
if(flag){
for(int i=0;i<n;i++) for(int j=0;j<m;j++) if(a[i][j]=='T'&&!is[i][j]) dfs(i,j);
}
if(is[n-1][m-1]) printf("Yes\n");
else printf("No\n");
}
}
```
:::
---
### 期末小抄
---
Text_editor(沒考 先不用看)
:::spoiler Cursor-way
```c=
#include<stdio.h>
#include<string.h>
#define MAX_SIZE 500
char content[MAX_SIZE],input[MAX_SIZE];
int cursor=0,rbound=-1,lbound=-1;
void backspace(void){
if(cursor==lbound+1) return;
else if(cursor==rbound+1) cursor--,rbound--;
else{
for(int i=cursor;i<=rbound;i++) content[i-1]=content[i];
cursor--,rbound--;
}
return;
}
void shift(void){
for(int i=rbound;i>=cursor;i--) content[i+1]=content[i];
return;
}
int main(){
while(fgets(input, MAX_SIZE, stdin)!=0){
int str=strlen(input);
for(int i=0;i<str;i++){
if(input[i]=='/'){
if(input[i+1]=='b'){
backspace();
i+=9;
}
else if(input[i+1]=='n'){
if(cursor!=rbound+1) shift();
content[cursor]='\n',cursor++,rbound++,i+=7;
}
else if(input[i+1]=='l'){
if(cursor!=lbound+1) cursor--;
i+=4;
}
else if(input[i+1]=='r'){
if(cursor!=rbound+1) cursor++;
i+=5;
}
}
else{
if(cursor!=rbound+1) shift();
content[cursor]=input[i],cursor++,rbound++;
}
}
for(int i=0;i<=rbound;i++) printf("%c", content[i]);
}
}
```
:::
:::spoiler Link-list
```c=
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
char pattern[505];
int str;
typedef struct node{
char c;
struct node *l, *r;
}Node;
void *insert(Node *a, char c){ //把b插入a與a後面的之間
Node *b = (Node*)malloc(sizeof(Node));
b->l = NULL, b->r = NULL, b->c = c;
if(a->r!=NULL) b->r = a->r, a->r->l = b; //將a後面的與b的接起
b->l = a, a->r = b; //將a與b接起
}
void erase(Node *a){ a->l->r = a->r; if(a->r!=NULL) a->r->l = a->l;}
int main(){
Node *head = (Node*)malloc(sizeof(Node)); //head 為開頭
head->r = NULL, head->l = head;
Node *cursor = head;
fgets(pattern,500,stdin), str = strlen(pattern);
for(int i=0;i<str;i++){
if(pattern[i]=='/'){
if(pattern[i+1]=='b') erase(cursor), cursor = cursor->l, i+=9;
else if(pattern[i+1]=='n') insert(cursor,'\n'), cursor = cursor->r, i+=7;
else if(pattern[i+1]=='l'){ if(cursor->l!=NULL) cursor = cursor->l; i+=4; }
else if(pattern[i+1]=='r'){ if(cursor->r!=NULL) cursor = cursor->r; i+=5; }
}
else insert(cursor,pattern[i]), cursor= cursor->r;
}
head = head->r;
while(head!=NULL) printf("%c",head->c), head = head->r;
}
```
:::
---
11773-Intger Pointer Array
:::spoiler pointer!
```c=
#include<stdlib.h>
#include<stdio.h>
int** malloc_ptr(int array_size){
int **ptr=(int **)malloc(sizeof(int*)*array_size);return ptr;
}
void malloc_array(int **array, int array_size){
*array=(int*)malloc(sizeof(int)*array_size);
}
void pointer_ptr_to_array(int *array, int **ptr,int N){
int in=1,j=0;
for(int i=0;i<N;i++) ptr[i]=&array[j],j+=in,in++;
}
```
:::
---
11490-Cat Society
:::spoiler Quick_Sort
```c=
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
typedef struct _cat{
char name[50];
int occu;
int age;
}cat;
int cmp(const void*a,const void *b){
cat A=*(cat *)a;cat B=*(cat *)b;
if(A.occu==B.occu){
if(A.age==B.age) return strcmp(A.name,B.name);
else if(A.age>B.age) return A.occu==5?1:-1;
else if(A.age<B.age) return A.occu==5?-1:1;
}
else if(A.occu>B.occu) return 1;
else if(A.occu<B.occu) return -1;
}
int main(){
int N,M;cat cats[10005];
while(~scanf("%d%d",&N,&M)){
for(int i=0;i<N;i++){
char temp[25];scanf("%s%s%d",cats[i].name,temp,&(cats[i].age));
switch(temp[0]){
case 'e': cats[i].occu=1;break;
case 'n': cats[i].occu=2;break;
case 'k': cats[i].occu=3;break;
case 'w': cats[i].occu=4;break;
case 'a': cats[i].occu=5;break;
case 'm': cats[i].occu=6;break;
case 'd': cats[i].occu=7;break;
case 'l': cats[i].occu=8;break;
}
}
qsort(cats,N,sizeof(cat),cmp);
for(int i=0;i<N&&i<M;i++) printf("%s\n",cats[i].name);
}
}
```
:::
---
12568-Reverse Linked List ver 2
:::spoiler Link-list!
```c=
#include"function.h"
void Push(Node** ptr_head, int x) {
Node* tr = (Node*) malloc(sizeof(Node));
tr->next = (*ptr_head),tr->data = x,(*ptr_head) = tr;
}
void Pop(Node** ptr_head) {
if( *ptr_head == NULL ) return;
Node* tmp = *ptr_head,*ptr_head = (*ptr_head)->next;
free(tmp);
}
void Reverse_List(Node** ptr_head) {
Node *a = NULL;
while(*ptr_head!=NULL) Push(&a,(*ptr_head)->data), Pop(ptr_head);
*ptr_head = a;
/*
if( *ptr_head == NULL ) return;
Node* tail = NULL, *tmp = NULL;
Node* head = *ptr_head;
while( head->next != NULL) {
tmp = head->next;
head->next = tail;
tail = head;
head = tmp;
}
head->next = tail;
*ptr_head = head;
*/
}
```
:::
---
12582-Function Pointer Practice
:::spoiler function pointer
```c=
#include <stdio.h>
#include <stdlib.h>
typedef struct{
void (*func)(void *);
void *argument;
}Task;
typedef struct{
int* arr;
int lower;
int upper;
}Data;
typedef struct{
Task **tasks;
int size;
}Task_List;
void job1(void* argument){
int l=((Data*)argument)->lower,r=((Data*)argument)->upper;//cast語法來轉換型別
while(1){
int tmp;tmp=((Data*)argument)->arr[l],
((Data*)argument)->arr[l]=((Data*)argument)->arr[r],
((Data*)argument)->arr[r]=tmp;
if(r-l<=1) break;
r--,l++;
}
}
void job2(void* argument){
int l=((Data*)argument)->lower,r=((Data*)argument)->upper;
while(l<=r) ((Data*)argument)->arr[l] *=-1,l++;
}
void job3(void* argument){
int l=((Data*)argument)->lower,r=((Data*)argument)->upper;
while(l<=r) ((Data*)argument)->arr[l] *=2,l++;
}
void initTask(Task* task, void(*func)(void*),void* argument){
task->func=func,task->argument=argument;
}
void executeTasks(Task_List *task_list){
for(int i=0;i<(task_list->size);i++){
task_list->tasks[i]->func(task_list->tasks[i]->argument);
}
}
```
:::
---
12584-The Beauty of Distributing
:::spoiler Recursion-DFS
```c=
#include<stdio.h>
#include<string.h>
#include<stdbool.h>
int n,box,a[1000];bool vis[1000];
bool dfs(int step,int sum){
if(step==n) return true;
for(int i=0;i<n;i++){
if(vis[i]) continue;
vis[i]=true;
if(sum+a[i]<box){if(dfs(step+1,sum+a[i])) return true;}
else if(sum+a[i]==box) {if(dfs(step+1,0)) return true;}
vis[i]=false;
}
return false;
}
int main(){
int T,sum,ans=0;scanf("%d",&T);
while(T--){
scanf("%d",&n);sum=0;
for(int i=0;i<n;i++) scanf("%d",&a[i]),sum+=a[i];
for(ans=n;ans>1;ans--){
box=sum/ans;
if(sum%ans==0){
memset(vis,false,sizeof(vis));
if(dfs(0,0)) break;
}
}
printf("%d\n",ans);
}
}
```
:::
---
13077-Ranking system
:::spoiler Malloc+linklist
```c=
#include"function.h"
#include<stdlib.h>
#include<string.h>
void Insert( Node** Table,int N,int score,char* name){
Node *a=(Node*)malloc(sizeof(Node));
a->name=(char*)malloc(sizeof(char)*101);
a->score=score,strcpy(a->name,name),Table[N]=a;
}
void Delete( Node** Table,int N,char* name){
for(int i=0;i<N;i++) if(strcmp(Table[i]->name,name)==0){
free(Table[i]->name),free(Table[i]);
Table[i]=Table[N-1],Table[N-1]=NULL;
break;
}
}
int* Top( Node** Table,int N,int x){
int *a=(int*)malloc(sizeof(int)*x);
for(int i=0;i<x;i++) a[i]=-1;
for(int i=0;i<N;i++)
for(int j=0;j<x;j++)
if(a[j]==-1||(Table[i]->score>Table[a[j]]->score)||
(Table[i]->score==Table[a[j]]->score)&&
strcmp(Table[i]->name,Table[a[j]]->name)<0){
for(int k=x-1;k>j;k--) a[k]=a[k-1];
a[j]=i;
break;
}
return a;
}
```
:::
---
13083-Bulid a VIM
:::spoiler Brute way
```c=
#include<stdio.h>
#include<stdbool.h>
#include<stdlib.h>
#define max(a,b) (a>b?a:b)
#define min(a,b) (a<b?a:b)
int main(){
char str[205];
while(scanf("%s",str)==1){
char ans[505]={'\0'};
int cursor=0,len=0,repeat=1;
bool mode=false;
for(int i=0;str[i]!='\0';i++){
if(str[i]==':'&&str[i+1]=='w'&&str[i+2]=='q'){
break;
}
if(!mode){
switch(str[i]){
case 'I':
cursor=0;
mode=true;
break;
case 'i':
mode=true;
break;
case 'A':
cursor=len;
mode=true;
break;
case 'a':
cursor+=(len!=0);
mode=true;
break;
case 'x':
repeat=min(repeat,len-cursor);
for(int j=cursor;j<len-repeat;j++) ans[j]=ans[j+repeat];
len=max(len-repeat,0);
cursor=max(min(cursor,len-1),0);
repeat=1;
break;
case 'h':
cursor-=repeat;
if(cursor<0) cursor=0;
repeat=1;
break;
case 'l':
cursor=max(min(cursor+repeat,len-1),0);
repeat=1;
break;
case '1' ... '9' :
repeat=str[i]-'0';
while(str[i+1]>='0'&&str[i+1]<='9') i++,repeat=repeat*10+str[i]-'0';
break;
default:
break;
}
}
else{
if(str[i]=='E'&&str[i+1]=='S'&&str[i+2]=='C'){
mode=false;
cursor=max(cursor-1,0);
}
else{
for(int j=len;j>cursor;j--) ans[j]=ans[j-1];
ans[cursor++]=str[i];
len++;
}
}
}
ans[len]='\0';
printf("%s\n",ans);
}
}
```
:::
---
13086-Golden ratio overheat
:::spoiler Recursion
``` c=
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
char f0[2005],f1[2005];long long int len[100];
char ar(int n,long long int k){
if(n==0) return f0[k];
if(n==1) return f1[k];
if(k>=len[n-2]) return ar(n-1,k-len[n-2]);
else ar(n-2,k);
}
int main(){
int T;scanf("%d",&T);
while(T--){
long long int n,k;scanf("%s%s%llu%llu",f0,f1,&n,&k);
len[0]=strlen(f0),len[1]=strlen(f1);
for (int i = 2;i<=n;i++) len[i]=len[i-1]+len[i-2];
char ans=ar(n,k);printf("%c\n",ans);
}
}
```
:::
### 寒假作業
10947 delete linked list
:::spoiler linked list + 題目要看懂
```c=
#include <stdlib.h>
#include <stdio.h>
typedef struct _Node {
int data;
struct _Node *next;
} Node;
void deleteNode(Node **head, int data){
if(data==1){*head=(*head)->next;return;}
Node *pre=NULL,*now=*head;data--;
while(now!=NULL&&data--) pre=now,now=now->next;
if(now) pre->next=now->next;
free(now);
}
Node* createList(){
int a;Node *head,*tail,*tmp;
scanf("%d",&a);
tmp=(Node*)malloc(sizeof(Node));
tmp->next=NULL,tmp->data=a;
head=tail=tmp;
while(scanf("%d",&a)&&a!=-1){
tmp=(Node*)malloc(sizeof(Node));
tmp->data=a,tmp->next=NULL;
tail->next=tmp,tail=tmp;
}
return head;
}
```
:::
---
12602 OuQ String
:::spoiler recursion
```c=
#include<stdio.h>
int k;long long l,r,tmp,len[53],r1;
void rec(int k){
if(tmp+len[k]<=l){tmp+=len[k];return;}
else if(tmp<=r){
if(tmp>=l&&tmp<=r) printf("O");
tmp++;
if(k!=1&&tmp<=r) rec(k-1);
if(tmp>=l&&tmp<=r) printf("u");
tmp++;
if(k!=1&&tmp<=r) rec(k-1);
if(tmp>=l&&tmp<=r) printf("Q");
tmp++;
}
else return;
}
long long lenk(int k){
if(len[k]) return len[k];
if(k==1) return len[1]=3;
return len[k]=3+2*lenk(k-1);
}
int main(){
lenk(50);
while(~scanf("%d%lld%lld\n",&k,&l,&r)) tmp=0,rec(k),printf("\n");
}
```
:::
---
12603 Launch of Collider
:::spoiler 水題
```c=
#include<stdio.h>
#define min(a,b) (a>b?b:a)
#define inf 2147483647
#define maxn 200005
char d[maxn];
int main(){
int n;int p,l=-1;int time=inf;
scanf("%d%s",&n,d);
for(int i=0;i<n;i++){
scanf("%d",&p);
if(d[i]=='R') {l=p;continue;}
if(l!=-1) time=min(time,(p-l)/2);
}
printf("%d\n",time==inf?-1:time);
}
```
:::
---
12604 Nqueen Mrook
:::spoiler advanced Nqueen
```c=
#include<stdio.h>
char board[12][12];
int init_board(int size){for(int i=0;i<size;i++) for(int j=0;j<size;j++) board[i][j]='0';}
int check_queen(int r,int c,int size){
for(int i=1;i<size;i++){
if(c-i>=0&&(board[r-i][c-i]=='Q'||board[r-i][c-i]=='R')) return 0;
if(c+i<size&&(board[r-i][c+i]=='Q'||board[r-i][c+i]=='R')) return 0;
if(board[r-i][c]=='Q'||board[r-i][c]=='R') return 0;
}
return 1;
}
int check_rook(int r,int c,int size){
for(int i=1;i<size;i++){
if(c-i>=0&&board[r-i][c-i]=='Q') return 0;
if(c+i<size&&board[r-i][c+i]=='Q') return 0;
if(board[r-i][c]=='Q'||board[r-i][c]=='R') return 0;
}
return 1;
}
int put_chess(int r,int n,int m,int N,int M,int size){
if(r==size) return 1;
int cnt=0;
for(int c=0;c<size;c++){
if(n<N&&check_queen(r,c,size)){
board[r][c]='Q';
cnt+=put_chess(r+1,n+1,m,N,M,N+M);
board[r][c]='0';
}
if(m<M&&check_rook(r,c,size)){
board[r][c]='R';
cnt+=put_chess(r+1,n,m+1,N,M,N+M);
board[r][c]='0';
}
}
return cnt;
}
int main(){
int N,M;
while(~scanf("%d%d",&N,&M)){
init_board(N+M);
printf("%d\n",put_chess(0,0,0,N,M,N+M));
}
}
```
:::
---
12605 Rebranding
:::spoiler There's no 'map' in C, but we can create one
```c=
#include<stdio.h>
#define maxn 200005
char s[maxn];
int alpha_idx[30];char map[30];
void swap_int(int *a,int *b){int tmp=*a;*a=*b;*b=tmp;}
void swap_char(char *a,char *b){char tmp=*a;*a=*b;*b=tmp;}
int main(){
int n,m;char c1,c2;
for(int i=0;i<26;i++){
alpha_idx[i]=i;
map[i]=(char)('a'+i);
}
scanf("%d%d%s",&n,&m,s);
for(int i=0;i<m;i++){
scanf(" %c %c",&c1,&c2);
swap_char(&map[alpha_idx[c1-'a']],&map[alpha_idx[c2-'a']]);
swap_int(&alpha_idx[c1-'a'],&alpha_idx[c2-'a']);
}
for(int i=0;i<n;i++) printf("%c",map[s[i]-'a']);
printf("\n");
}
```
:::
---
12606 Happy New Year
:::spoiler 水題
```c=
#include<stdio.h>
#define inf 2147483647
int main(){
int n,x,mx=-1,mn=inf;
scanf("%d",&n);
for(int i=0;i<=n;i++){
scanf("%d",&x);
mx=x>mx?x:mx;
mn=x<mn?x:mn;
}
printf("%d\n",2*(mx-mn));
}
```
:::
---
12611 The same calender
:::spoiler 同月同日
```c=
#include<stdio.h>
#include<stdlib.h>
int is_leap(int n){
return (!(n%400)||(!(n%4)&&n%100))?1:0;
}
int main(){
int n,year;
scanf("%d",&n);
while(n--){
scanf("%d",&year);
int same=0,is_leap_ori=is_leap(year);
same+=is_leap(++year)?366%7:365%7;
while(same||is_leap_ori^is_leap(year)){
same+=is_leap(++year)?366%7:365%7;
same%=7;
}
printf("%d\n",year);
}
}
```
```c=
#include<stdio.h>
int t,yy,y,num;
int leap(int y){return (y%400==0||(y%4==0&&y%100));}
int main(){
scanf("%d",&t);
while(t--){
scanf("%d",&y);
yy=y,num=0;
do{
num+=leap(yy)+1,yy++;
}while(num%7||leap(yy)!=leap(y));
printf("%d\n",yy);
}
}
```
:::
---
12612 Querues on a string
:::spoiler strncpy
```c=
#include<stdio.h>
#include<string.h>
char s[10005],sub_s[10005];int l,r,t,len;
int main(){
int m;scanf("%s%d",s,&m);
while(m--){
scanf("%d%d%d",&l,&r,&t);
l--,r--;
len=r-l+1;
strncpy(sub_s,s+l,len);
for(int i=0;i<len;i++) s[l+(i+t)%len]=sub_s[i];
}
printf("%s\n",s);
}
```
:::
---
12613 Yet another meme problem
:::spoiler 數學問題 符合題意的數字只會在“b是10的n次方-1的情況下“(n是任意自然數)
```c=
#include<stdio.h>
#include<math.h>
int main(){
int t,a,b;scanf("%d",&t);
while(t--){
scanf("%d%d",&a,&b);
printf("%.0f\n",a*floor(log10(b+1)));
}
}
```
:::
---
12614 Game Shopping
:::spoiler 不要用for迴圈來寫，會錯
```c=
#include<stdio.h>
#define maxn 1005
int c[maxn],a[maxn];
int main(){
int n,m,t=0,newa=0,newc=0;scanf("%d%d",&n,&m);
for(int i=0;i<n;i++) scanf("%d",&c[i]);
for(int i=0;i<m;i++) scanf("%d",&a[i]);
while(newc<n){
if(a[newa]>=c[newc]){
t++,newc++,newa++;continue;
}
else if(a[newa]<c[newc]) newc++;
}
printf("%d\n",t);
}
```
```c=
#include<stdio.h>
int n,m,a[1005],b[1005],p=0;
int main(){
scanf("%d%d",&n,&m);
for(int i=0;i<n;i++) scanf("%d",&a[i]);
for(int i=0;i<m;i++) scanf("%d",&b[i]);
for(int i=0;i<n;i++) if(p<m&&b[p]>=a[i]) p++;
printf("%d\n",p);
}
```
:::
---
12616 Knight Search
:::spoiler 一維轉二維
```c=
#include<stdio.h>
char r[110][110];
char as[13]="ICPCASIASG";
int n,flag;
// now是當前位置(以一維紀錄二維);prog是進度，代表我已經到第幾個想要的字了。
void rec(int now,int prog){
if(prog==10) {flag=1;return;}
for(int i=-2;i<=2&&!flag;i++) for(int j=-2;j<=2&&!flag;j++){
if(j*j+i*i!=5||now/n+i<0||now/n+i>=n||now%n+j<0||now%n+j>=n) continue;
if(r[now/n+i][now%n+j]==as[prog]) rec(now+i*n+j,prog+1);
}
}
int main(){
scanf("%d\n",&n);//多讀一個換行很重要
for(int i=0;i<n;i++) for(int j=0;j<n;j++) scanf("%c",&r[i][j]);
flag=0;int cnt=-1;
while(cnt<n*n&&!flag){
cnt++;if(r[cnt/n][cnt%n]==as[0]) rec(cnt,1);
}
printf("%s\n",(flag?"YES":"NO"));
}
```
:::
---
## 程設二
12668 Text editor in doubly linked list
:::spoiler 要讀到換行！
```c=
#include<stdio.h>
#include<stdlib.h>
typedef struct _Node{
char ch;
struct _Node *prev;
struct _Node *next;
}Node;
void backspace(Node** ptr){
Node* now=*ptr;
if(now->prev==NULL) return;
if(now->next==NULL){
*ptr=now->prev;
(*ptr)->next=NULL;
free(now);
}
else{
now->next->prev=now->prev;
now->prev->next=now->next;
*ptr=now->prev;
free(now);
}
}
void insert(Node** ptr,char c){
Node* now=*ptr;
Node* newone=(Node*)malloc(sizeof(Node));
newone->ch=c,newone->prev=now,newone->next=now->next;
if(now->next!=NULL) now->next->prev=newone;
now->next=newone;*ptr=newone;
}
void print(Node* head){
Node* now=head->next;
while(now!=NULL){
printf("%c",now->ch);
Node* tmp=now;
now=now->next;
free(tmp);
}
free(head);printf("\n");
}
int main(){
int t;scanf("%d",&t);
while(t--){
Node* head=(Node*)malloc(sizeof(Node));
head->prev=NULL;head->next=NULL;
Node* now=head;
int n;scanf("%d\n",&n);
while(n--){
char input;input=getchar();
if(input=='L'){if(now->prev!=NULL) now=now->prev;}
else if(input=='B'){backspace(&now);}
else if(input=='R'){if(now->next!=NULL) now=now->next;}
else{insert(&now,input);}
}
print(head);
}
}
```
```c=
#include<stdio.h>
#include<stdlib.h>
int t,n;
char s[1000005];
typedef struct _Node{
char c;
struct _Node *l, *r;
}Node;
main(){
scanf("%d",&t);
while(t--){
scanf("%d%s",&n,s);
Node *head = (Node*)malloc(sizeof(Node)), *now = head, *tmp;
head->l = head->r = NULL;
for(int i=0;i<n;i++){
if(s[i]=='L') now = now->l;
else if(s[i]=='R') now = now->r;
else if(s[i]=='B'){
tmp = now, now->l->r = now->r;
if(now->r) now->r->l = now->l; //now->r有可能為空
now = now->l;
free(tmp);
}
else{
Node *N = (Node*)malloc(sizeof(Node));
if(now->r!=NULL) now->r->l = N; //now->r有可能為空
N->c = s[i], N->l = now, N->r = now->r, now->r = N, now = now->r;
}
}
while(head->r) head = head->r, printf("%c",head->c), free(head->l);
printf("\n");
}
}
```
:::
---
12680 Card Magic
:::spoiler doubly linked list
```c=
#include <stdio.h>
#include <stdlib.h>
#include "function.h"
Node* ReadOneList(){
Node* head=(Node*)malloc(sizeof(Node));scanf("%d: ",&(head->size));
head->data=(int*)malloc(head->size*sizeof(int));
for(int i=0;i<(head->size);i++) {int x;scanf("%d",&x);getchar();*((head->data)+i)=x;}
head->next = NULL;return head;
}
void PrintList(Node* head) {
head=head->next;
while(head!=NULL) {
printf("%d",*(head->data));
for(int i=1;i<(head->size);i++) printf(" %d",*((head->data)+i));
printf("\n");Node* temp=head;head=head->next;
}
}
void Merge(Node* head, int x, int y) {
if(x==y) return;
Node* prev_x=head;Node* temp_x=prev_x->next;
Node* prev_y=head;Node* temp_y=prev_y->next;
x--;y--;
while(x--) {prev_x=prev_x->next;temp_x=temp_x->next;if(temp_x==NULL) return;}
while(y--) {prev_y=prev_y->next;temp_y=temp_y->next;if(temp_y==NULL) return;}
Node* new_head=(Node*)malloc(sizeof(Node));
new_head->size=temp_x->size+temp_y->size;
new_head->data=(int*)malloc((new_head->size)*sizeof(int));
int i;for(i=0;i<temp_y->size;i++) *((new_head->data)+i)=*((temp_y->data)+i);
for(int j=0;j<temp_x->size;j++) *((new_head->data)+i+j)=*((temp_x->data)+j);
if(temp_y==prev_x) {prev_y->next=new_head;new_head->next=temp_x->next;}
else if(temp_x==prev_y) {prev_x->next=new_head;new_head->next=temp_y->next;}
else {prev_y->next=new_head;new_head->next=temp_y->next;prev_x->next=temp_x->next;}
free(temp_x->data);free(temp_x);free(temp_y->data);free(temp_y);
}
void Cut(Node* head, int x, int y) {
Node* prev=head;Node* temp=head->next;
x--;while(x--) {prev=prev->next;temp=temp->next;}
if(temp->size<2) return;
int size_1=y;int size_2=temp->size - y;
Node* new_head_1=(Node*)malloc(sizeof(Node));
Node* new_head_2=(Node*)malloc(sizeof(Node));
new_head_1->size=size_1;new_head_2->size=size_2;
new_head_1->data=(int*)malloc(new_head_1->size*sizeof(int));
new_head_2->data=(int*)malloc(new_head_2->size*sizeof(int));
int i;for(i=0;i<new_head_1->size;i++) *(new_head_1->data+i)=*(temp->data+i);
for(int j=0;j<new_head_2->size;j++) *(new_head_2->data+j)=*(temp->data+i+j);
prev->next=new_head_1;new_head_1->next=new_head_2;new_head_2->next=temp->next;
free(temp->data);free(temp);
}
```
```c=
#include "function.h"
#include<stdlib.h>
Node* ReadOneList(){
Node *a = (Node*)malloc(sizeof(Node));
scanf("%d:",&a->size);
a->data = (int*)malloc(sizeof(int)*a->size);
for(int i=0;i<a->size;i++) scanf("%d",&a->data[i]);
a->next = NULL;
return a;
}
void PrintList(Node* now){
while(now->next){
now = now->next;
for(int i=0;i<now->size;i++) printf("%d%c",now->data[i],i==now->size-1?'\n':' ');
}
}
void Merge(Node* head, int pa, int pb){
int cnt = 0;
Node *a,*b,*last = head; //last 是a的前一個
while(head){
head = head->next, cnt++;
if(cnt==pa) a = head; //找a
if(cnt<pa) last = head; //找a的前一個
if(cnt==pb) b = head; //找b
}
int *bdata = b->data; //先複製b的data
b->data = (int*)malloc(sizeof(int)*(a->size+b->size)); //將b開大
for(int i=0;i<b->size;i++) b->data[i] = bdata[i];
for(int i=0;i<a->size;i++) b->data[i+b->size] = a->data[i];
last->next = a->next, b->size += a->size, free(a->data), free(a), free(bdata); //將a的前面街上後面
}
void Cut(Node* head, int pa, int x){
while(pa--) head = head->next;
Node *a = (Node*)malloc(sizeof(Node));
a->size = head->size-x, a->data = (int*)malloc(sizeof(int)*a->size);
for(int i=0;i<a->size;i++) a->data[i] = head->data[x+i];
head->size = x, a->next = head->next, head->next = a;
}
```
:::
---
13133 - Got You! JerryFish!
:::spoiler 直接交換
```c=
#include"function.h"
void createLinkedList(Node **head, int N, int *arr){
Node *now=(Node*)malloc(sizeof(Node));
now->val=arr[1];*head=now;
for(int i=2;i<=N;i++) {
now->next=(Node*)malloc(sizeof(Node));
now=now->next;
now->val=arr[i];
}
now->next=*head;
}
void swapTwoSegment(Node **head, int a, int b, int len){
Node *A=*head,*B=*head;
while(--a) A=A->next;
while(--b) B=B->next;
while(len--){
int tmp=A->val;
A->val=B->val,B->val=tmp,A=A->next,B=B->next;
}
}
```
:::
---
13134 - Band Ya Rou Ze
:::spoiler 上標下標法
```c=
#include<stdio.h>
#define mx 2000005
#define swap(a,b) (a^=b^=a^=b)
int n,a,b,c,rh[100005],re[100005],r[mx],p,now;
char s[mx];////rh紀錄每行開頭，re結尾，沒東西為0
int main(){
scanf("%d",&n);
for(int i=1;i<n+1;i++){
scanf(" %d ",&a);rh[i]=(a?p+1:a),re[i]=(a?p+a:a);
for(int i=0;i<a;i++){
scanf("%c",&s[++p]);
i?r[now]=p:0;
now=p;
}
}
scanf("%d",&p);
while(p--){
scanf("%d%d%d",&c,&a,&b);
if(c==1&&re[a]){
if(rh[b]==0) re[b]=re[a];
r[re[a]]=rh[b],rh[b]=rh[a],rh[a]=re[a]=0;
}
if(c==2&&re[a]){
if(rh[b]==0) rh[b]=rh[a],re[b]=re[a],rh[a]=re[a]=0;
else r[re[b]]=rh[a],re[b]=re[a],rh[a]=re[a]=0;
}
if(c==3){
swap(rh[a],rh[b]),swap(re[a],re[b]);
}
}
now=0;
for(int i=1;i<n+1;i++){
now=rh[i];
while(now) printf("%c",s[now]),now=r[now];
printf("\n");
}
}
```
```c=
#include<stdio.h>
#include<stdlib.h>
typedef struct _node{
char *c;
struct _node *next;
}Node;
int n,a,b,c,t;
Node *rh[100005],*re[100005],*tmp;
int main(){
scanf("%d",&n);
for(int i=1;i<n+1;i++){
scanf("%d",&a);rh[i]=re[i]=NULL;
if(a){
rh[i]=re[i]=(Node*)malloc(sizeof(Node)); //careful!!
rh[i]->c=(char*)malloc(sizeof(char)*(a+1));
scanf("%s",rh[i]->c);rh[i]->next=NULL;
}
}
scanf("%d",&t);
while(t--){
scanf("%d%d%d",&c,&a,&b);
if(c==1&&re[a]){
if(rh[b]==NULL) re[b]=re[a];
re[a]->next=rh[b],rh[b]=rh[a],rh[a]=re[a]=NULL;//careful!!
}
if(c==2&&re[a]){
if(rh[b]==NULL) rh[b]=rh[a],re[b]=re[a],rh[a]=re[a]=NULL;
else re[b]->next=rh[a],re[b]=re[a],rh[a]=re[a]=NULL;
}
if(c==3) {tmp=rh[a],rh[a]=rh[b],rh[b]=tmp,tmp=re[a],re[a]=re[b],re[b]=tmp;}
}
for(int i=1;i<n+1;i++){
while(rh[i]!=NULL) {printf("%s",rh[i]->c);rh[i]=rh[i]->next;}
printf("\n");
}
}
```
:::
---
11847 - Prefix Boolean expression
:::spoiler malloc+'&'+'|'+recursion function
```c=
#include<stdio.h>
#include<stdlib.h>
typedef struct _node{
char c;
struct _node *l,*r;
}Node;
Node *build(Node* head){
char c;scanf("%c",&c);
Node *n=(Node*)malloc(sizeof(Node));
n->r=n->l=NULL,n->c=c;
if(c=='|'||c=='&') n->l=build(n->l),n->r=build(n->r);
return n;
}
int solve(Node* head,int v){
if(head->c=='&') return solve(head->r,v)&solve(head->l,v);
else if(head->c=='|') return solve(head->r,v)|solve(head->l,v);
else return (v>>(3-(head->c-'A')))&1;
}
int main(){
Node *s=NULL;s=build(s);
for(int i=0;i<16;i++) printf("%d %d %d %d %d\n",(i>>3)&1,(i>>2)&1,(i>>1)&1,i&1,solve(s,i));
}
```
:::
---
10966 - Infix to syntax tree
:::spoiler 按照規矩寫，不要偷吃步
```c=
#ifndef FUNCTION_H
#define FUNCTION_H
#include<stdlib.h>
#include<stdio.h>
#define MAXEXPR 256
#define NUMSYM 6
char expr[MAXEXPR]; // string to store the input expression.
int pos; // current position of parsing, from end to start
typedef enum {ID_A, ID_B, ID_C, ID_D, OP_AND, OP_OR} TokenSet;
char sym[NUMSYM];
typedef struct _Node {
TokenSet data;
struct _Node *left, *right;
} BTNode;
BTNode* EXPR();
BTNode* FACTOR();
BTNode* makeNode(char c){
BTNode *node=(BTNode*)malloc(sizeof(BTNode));
switch(c){
case('A'):
node->data=ID_A,node->right=NULL,node->left=NULL;break;
case('B'):
node->data=ID_B,node->right=NULL,node->left=NULL;break;
case('C'):
node->data=ID_C,node->right=NULL,node->left=NULL;break;
case('D'):
node->data=ID_D,node->right=NULL,node->left=NULL;break;
case('&'):
node->data=OP_AND;break;
case('|'):
node->data=OP_OR;break;
}
return node;
}
BTNode* EXPR(){
BTNode *r=FACTOR();
if(pos==-1||expr[pos]=='(') return r;
BTNode *n=makeNode(expr[pos--]);
n->right=r,n->left=EXPR();
return n;
}
BTNode* FACTOR(){
char c=expr[pos--];
BTNode *n;
if(c==')'){n=EXPR(),pos--;return n;}
else return makeNode(c);
}
#endif
```
:::
---
10968 - Prefix to infix
:::spoiler 遞迴＋括號的問題
```c=
#ifndef FUNCTION_H
#define FUNCTION_H
#include<stdlib.h>
#include<stdio.h>
typedef struct treeNode {
char data;
struct treeNode *left;
struct treeNode *right;
} Node;
void printInfix(Node *root){
if(root->left != NULL) printInfix(root->left);
printf("%c", root->data);
if(root->right != NULL){
if(root->right->data == '|' || root->right->data == '&') printf("(");
printInfix(root->right);
if(root->right->data == '|' || root->right->data == '&') printf(")");
}
}
#endif
```
:::
---
10972 - Remove unnecessary parentheses
:::spoiler 重建一棵樹
```c=
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
typedef struct _node{
char c;
struct _node *r,*l;
}Node;
char s[300],d[10]="ABCD|&";
int len;
Node* ex(void);
Node* add(char);
Node* fa(void){ //factor
Node *t=NULL;char aa; //t==tmp
if(len>=0){
aa=s[len--];
if(aa>='A'&&aa<='D') t=add(aa);
else if(aa==')'){
t=ex();if(s[len--]!='(') return NULL;
}
}
return t;
}
Node* ex(void){ //expression==expr
Node *ri,*root; //ri==right
if(len>=0){
ri=fa();
if(len>0){
char t=s[len]; //t==tmp
if(t=='&'||t=='|') root=add(t),len--,root->r=ri,root->l=ex();
else root=ri;
}
else root=ri;
}
return root;
}
Node* add(char c){ //makeNode
Node *t=(Node*)malloc(sizeof(Node)); //t==tmp
for(int i=0;i<6;i++) if(c==d[i]){t->c=d[i];break;}
t->r=t->l=NULL;
return t;
}
void P(Node* h){ //print
if(h->l!=NULL) P(h->l);//h==head
printf("%c",h->c);
if(h->r!=NULL){
if(h->r->c=='&'||h->r->c=='|') printf("(");
P(h->r);
if(h->r->c=='&'||h->r->c=='|') printf(")");
}
}
int main(){
scanf("%s",s);
len=strlen(s)-1;
Node *root=ex();
P(root);
}
```
:::
---
13139 - Binary Patrick Star
:::spoiler 叫一個雙星的Node,之後再給雙星Node接左邊接右邊
```c=
#include"function.h"
#include<stdlib.h>
Node* buildBinaryTree(int n, int* lch, int* rch){
Node **node=(Node**)malloc(sizeof(Node*)*n);
for(int i=0;i<n;i++) node[i]=(Node*)malloc(sizeof(Node));
for(int i=0;i<n;i++){
node[i]->id=i,
node[i]->left=(lch[i]==-1)?NULL:node[lch[i]],
node[i]->right=(rch[i]==-1)?NULL:node[rch[i]];
}
Node *head=node[0];
free(node);return head;
}
void Traversal(Node* head, int* sz){
sz[head->id]=1;
if(head->left) Traversal(head->left,sz),sz[head->id]+=sz[head->left->id];
if(head->right) Traversal(head->right,sz),sz[head->id]+=sz[head->right->id];
}
void freeBinaryTree(Node* root){
if(root->left) freeBinaryTree(root->left);
if(root->right) freeBinaryTree(root->right);
free(root);
}
```
```c=
//Lab
#include<stdlib.h>
#define max(a,b) (a>b?a:b)
typedef struct _Node {
struct _Node *left, *right;
int id;
} Node;
Node* buildBinaryTree(int, int*, int*);
void Traversal(Node*, int*);
void freeBinaryTree(Node*);
Node* buildBinaryTree(int n, int* lch, int* rch){
Node **node=(Node**)malloc(sizeof(Node*)*n);
for(int i=0;i<n;i++) node[i]=(Node*)malloc(sizeof(Node));
for(int i=0;i<n;i++){
node[i]->id=i,
node[i]->left=(lch[i]==-1)?NULL:node[lch[i]],
node[i]->right=(rch[i]==-1)?NULL:node[rch[i]];
}
Node *head=node[0];
free(node);return head;
}
void Traversal(Node* head, int* depth){
int r=0,l=0;
if(head->left) Traversal(head->left,depth),l+=depth[head->left->id]+1;
else l=1;
if(head->right) Traversal(head->right,depth),r+=depth[head->right->id]+1;
else r=1;
depth[head->id]=max(r,l);
}
void freeBinaryTree(Node* root){
if(root->left) freeBinaryTree(root->left);
if(root->right) freeBinaryTree(root->right);
free(root);
}
```
:::
---
13140 - Wubalubadubdub
:::spoiler 不用真的把樹建出來
```c=
#include<stdio.h>
int a[200005],n=0;
void rec(int tim,int level){
if(tim>level) return;
printf("%s%d",(level!=n-2?" ":""),a[level]);
int aa=tim,bb=level;
while(aa<bb){
if(a[(aa+bb)/2]<a[level]) aa=(aa+bb)/2+1;
else bb=(aa+bb)/2;
}
rec(tim,aa-1),rec(aa,level-1);
}
int main(){
while(~scanf("%d",&a[n++]));
rec(0,n-2),printf("\n");
}
```
:::
---
---
12720 - Binary search trees II: pruning
:::spoiler traversal+valid
```c=
#include<stdio.h>
#include<stdlib.h>
#define max(a,b) (a>b?a:b)
typedef struct _node{
int data,depth;
struct _node *r,*l;
}Node;
Node *a[101110],*root;
int n;
void valid(Node* head,int mi,int ma){
if(head==NULL) return;
if(head->data<mi||head->data>ma){ head->data=0;return;}
if(head->l!=NULL) valid(head->l,mi,head->data);
if(head->r!=NULL) valid(head->r,head->data,ma);
}
int traversal(Node* root){
if(root==NULL) return 0;
if(root->data!=0){traversal(root->l),traversal(root->r);}
else{
if(root->l!=NULL) root->l->data=0;
if(root->r!=NULL) root->r->data=0;
if(root->l==NULL&&root->r==NULL) return root->depth=1;//position!!
int _l=traversal(root->l),_r=traversal(root->r);
return root->depth+=max(_l,_r)+1;//'+='!!
}
return 1;
}
int main(){
scanf("%d\n",&n);
for(int i=1;i<=n;i++){//start from 1 !!
int t;scanf("%d ",&t);
Node* tt=(Node*)malloc(sizeof(Node));
a[i]=tt,tt->data=t,tt->depth=0,tt->r=tt->l=NULL;
}
int cnt=1;
while(cnt<=n){
int id=0;
char cc=getchar();
if(cc==' ') continue;
if(cc=='0') {root=a[cnt++];continue;}
while((int)(cc-'0')>=0&&(int)(cc-'0')<=9){
id*=10;id+=(int)(cc-'0');//(int)(cc-'0')!!
cc=getchar();
}
if(cc=='L') a[id]->l=a[cnt++];
else if(cc=='R') a[id]->r=a[cnt++];
}
valid(root,-1,2147000000);
traversal(root);
for(int i=1;i<n;i++) printf("%d ",a[i]->data!=0?a[i]->data:-(a[i]->depth));
printf("%d\n",a[n]->data!=0?a[n]->data:-(a[n]->depth));
}
```
:::
---
11840 - Moving books
:::spoiler returnbook + sendbook + (num/100)->在哪個桌子 + (num%100)->在桌子的哪裡
```c=
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
int id[25]={0},table[25][25]={0};
void send(int num,int to){
int j;for(j=0;table[to][j]!=-1;j++){}
table[to][j]=num,table[id[num]/100][id[num]%100]=-1,id[num]=to*100+j;
}
void re(int num){
int aa=id[num]/100,bb=id[num]%100;
for(int i=bb+1;table[aa][i]!=-1;i++) send(table[aa][i],table[aa][i]);
}
int main(){
int n,a,b;
char str1[5],str2[5];
scanf("%d",&n);
for(int i=0;i<n;i++) id[i]=i*100;
for(int i=0;i<n;i++){
table[i][0]=i;for(int j=1;j<n;j++) table[i][j]=-1;
}
while(scanf("%s",str1)){
if(strcmp(str1,"exit")==0) break;
scanf("%d%s%d",&a,str2,&b);
if(a==b||id[a]/100==id[b]/100) continue;
if(strcmp(str1,"move")==0&&strcmp(str2,"onto")==0) re(a),re(b),send(a,id[b]/100);
if(strcmp(str1,"move")==0&&strcmp(str2,"over")==0) re(a),send(a,id[b]/100);
if(strcmp(str1,"pile")==0&&strcmp(str2,"onto")==0){
re(b);int aa=id[a]/100;//不能放進去for裡面
for(int i=id[a]%100;table[aa][i]!=-1;i++) send(table[aa][i],id[b]/100);
}
if(strcmp(str1,"pile")==0&&strcmp(str2,"over")==0){
int aa=id[a]/100;//不能放進去for裡面
for(int i=id[a]%100;table[aa][i]!=-1;i++) send(table[aa][i],id[b]/100);
}
}
for(int i=0;i<n;i++){
printf("%d:",i);
for(int j=0;table[i][j]!=-1;j++) printf(" %d",table[i][j]);
printf("\n");
}
}
```
```c=
#include<stdio.h>
#define REP(i,j,k) for(int i=j;i<k;i++)
int n,a,b,table[30][30],book[30],top[30]; //table: 桌子上的書，book: 每本在哪張，top: 每桌高度
char s[5],t[5];
void move(int a,int b){ //move a to b, if b==0 mean go home
int ok = 0, A = book[a], sz = top[A]; //ok: 在a上(包含a), A: a的桌子
REP(i,0,sz){
if(table[A][i]==a) ok = 1;
if(ok && (table[A][i]!=a || b)){
int home = (b?book[b]:table[A][i]);
table[home][top[home]] = table[A][i], book[table[A][i]] = home,
top[home]++, top[A]--, table[A][i] = 0;
}
}
}
main(){
scanf("%d",&n);
REP(i,1,n+1) table[i][0] = book[i] = i, top[i] = 1;
while(scanf("%s",s) && s[0]!='e'){
scanf("%d%s%d",&a,t,&b), a++, b++;
if(book[a]==book[b]) continue;
if(s[0]=='m') move(a,0);
if(t[1]=='n') move(b,0);
move(a,b);
}
REP(i,0,n){
printf("%d:",i);
REP(j,0,top[i+1]) printf(" %d",table[i+1][j]-1);
printf("\n");
}
}
```
:::
---
11891 - Postfix to Syntax Tree
:::spoiler 是 "*head=s"; 不是 "head=&s";
```c=
#include"function.h"
Node* build(){
Node* newone=(Node*)malloc(sizeof(Node));
newone->data=s2[idx++],newone->right=NULL,newone->left=NULL;//newone->data!!
if(newone->data=='|'||newone->data=='&') newone->right=build(),newone->left=build();
return newone;
}
void constructTree(Node** head){
Node* s=build();*head=s;
}
```
```c=
#include "function.h"
void constructTree(Node** head){
Node *o = (Node*)malloc(sizeof(Node));
o->data = s2[idx++], o->right = o->left = NULL, *head = o;
if(o->data=='|' || o->data=='&') constructTree(&o->right), constructTree(&o->left);
}
```
:::
---
12725 - Minimum Spinning Tree
:::spoiler 先算好data的值，要用的時候再拿出來
```c=
#include<stdio.h>
#include<stdlib.h>
typedef struct _node{
char c;
int data;
struct _node *l,*r;
}Node;
Node* makenode(char c){
Node* newone=(Node*)malloc(sizeof(Node));
newone->c=c,newone->l=NULL,newone->r=NULL,newone->data=0;
return newone;
}
void solve(Node* root){
if(root->c=='+') root->data=root->l->data+root->r->data;
else if(root->c=='-') root->data=root->l->data-root->r->data;
else if(root->c=='*') root->data=root->l->data*root->r->data;
}
Node* build(){
char c=getchar();
if(c=='\n') return NULL;
Node* newone=makenode(c);
if(c=='+'||c=='-'||c=='*'){
newone->l=build(),newone->r=build(),solve(newone);
}
else newone->data=newone->c-'0';
return newone;
}
Node* copy(Node* root){
if(root==NULL) return NULL;
Node* newone=makenode(root->c);
newone->data=root->data;
newone->l=copy(root->l),newone->r=copy(root->r);
return newone;
}
Node* left(Node* root){
Node *newone,*newone_l,*newone_l_r;
newone=root->r;
newone_l=root;
newone_l_r=root->r->l;
newone->l=newone_l;
newone_l->r=newone_l_r;
return newone;
}
Node* right(Node* root){
Node *newone,*newone_r,*newone_r_l;
newone=root->l;
newone_r=root;
newone_r_l=root->l->r;
newone->r=newone_r;
newone_r->l=newone_r_l;
return newone;
}
void freeone(Node* root){
if(root==NULL) return;
freeone(root->l),freeone(root->r);free(root);
}
int main(){
int n;scanf("%d",&n);getchar();//getchar()!!
Node *root_l=build(),*root_r=copy(root_l);
int ans=root_l->data;
while(root_l->r->c=='+'||root_l->r->c=='-'||root_l->r->c=='*'){
root_l=left(root_l),solve(root_l->l),solve(root_l);
if(root_l->data<ans) ans=root_l->data;//root_l->data<ans!!
}
while(root_r->l->c=='+'||root_r->l->c=='-'||root_r->l->c=='*'){
root_r=right(root_r),solve(root_r->r),solve(root_r);
if(root_r->data<ans) ans=root_r->data;//root_r->data<ans!!
}
printf("%d\n",ans),freeone(root_l),freeone(root_r);return 0;
}
```
```c=
#include<stdio.h>
#define MX 300005
int ans=1e9,l[MX],r[MX],num[MX],p=1,L,R;
char s[MX];
void calc(int now){
if(s[now]=='+') num[now] = num[l[now]] + num[r[now]];
if(s[now]=='-') num[now] = num[l[now]] - num[r[now]];
if(s[now]=='*') num[now] = num[l[now]] * num[r[now]];
}
int dfs(){ //p:字串s下標
int now = p;
if(s[now]<'0') p++, l[now] = dfs(), p++, r[now] = dfs(), calc(now);
else num[now] = s[now]-'0';
return now;
}
main(){
scanf("%d%s",&p,s+1), p = 1; //p:字串s下標
dfs(), ans = num[1], p = 1; //p:現在為頭
while(l[p] && s[l[p]]<'0'){ //往左走到底
L = l[p], l[p] = r[L], calc(p); //L:左邊新頭
r[L] = p, calc(L), p = L;
if(num[p]<ans) ans = num[p];
}
while(r[p] &&s[r[p]]<'0'){ //往右走到底
R = r[p], r[p] = l[R], calc(p); //R:右邊新頭
l[R] = p, calc(R), p = R;
if(num[p]<ans) ans = num[p];
}
printf("%d\n",ans);
}
```
:::
---
13154 - Bee cover rain
:::spoiler 用題目給的公式來處理，並不需要建樹
```c=
#include<stdio.h>
long long p,q;char c;
long long f(void){
long long a,b;
scanf(" %c",&c);//space!!
if(c=='f'){
scanf("("),a=f(),scanf(","),b=f(),scanf(")");
return ((p*a)%q+b)%q;
}
else{
ungetc(c,stdin);
scanf("%lld",&a);
return a%q;
}
}
int main(){
scanf("%lld%lld",&p,&q);
p%=q;
printf("%lld\n",f());
}
```
:::
---
13155 - Maxmax tree operation
:::spoiler findMax用recursion
```c=
#include<stdlib.h>
struct Node {
int id;
struct Node *next;
};
struct Graph {
int vertices_num;
struct Node **adjLists;
};
struct Graph* createGraph(int n){
struct Graph *g=(struct Graph*)malloc(sizeof(struct Graph));
g->adjLists=(struct Node**)malloc(sizeof(struct Node*)*(n));
for(int i=0;i<n;i++) g->adjLists[i]=NULL;
g->vertices_num=n;
return g;
}
void addEdge(struct Graph* g, int a, int b){
struct Node *it=g->adjLists[a];
g->adjLists[a]=(struct Node*)malloc(sizeof(struct Node));
g->adjLists[a]->id=b;g->adjLists[a]->next=it;//!!!
it=g->adjLists[b];
g->adjLists[b]=(struct Node*)malloc(sizeof(struct Node));
g->adjLists[b]->id=a;g->adjLists[b]->next=it;//!!!
}
int findMax(struct Graph* g, int now, int pre){
int ans=now,a;
for (struct Node *it = g->adjLists[now]; it; it = it->next) {
if(it->id!=pre) a=findMax(g,it->id,now),a>ans?ans=a:0;//ans<a!!!
}
return ans;
}
void freeGraph(struct Graph* g){
for(int i=0;i<g->vertices_num;i++){
for(struct Node *it=g->adjLists[i];it;){
struct Node *nt=it->next;
free(it);it=nt;
}
}
free(g->adjLists);
free(g);
}
```
:::
---
---
13156 - Guess Left or Right
:::spoiler 陣列寫法
```c=
#include <stdio.h>
#include <stdlib.h>
#define MAXN 200002
int lch[MAXN], rch[MAXN],node_index[MAXN],point_to[MAXN],inorder[MAXN],ans[MAXN],root, idx;
void traverse(int node) {
if(node) traverse(lch[node]),ans[idx++] = node,traverse(rch[node]);
}
int main() {
int N;
while(scanf("%d", &N) != EOF) {
for(int i=1; i<=N; i++) {
scanf("%d %d", &lch[i], &rch[i]);
point_to[lch[i]] += 1,point_to[rch[i]] += 1;
}
for(int i=1; i<=N; i++) {
scanf("%d", &inorder[i]);node_index[inorder[i]] = i;
}
for(int i=1; i<=N; i++) if(!point_to[i]) {root = i;break;}
for(int i=1; i<=N; i++) {
int tmp;
if(lch[i] != 0 && node_index[lch[i]] > node_index[i]) {
tmp = lch[i],lch[i] = rch[i],rch[i] = tmp;
}
if(rch[i] != 0 && node_index[rch[i]] < node_index[i]) {
tmp = rch[i],rch[i] = lch[i],lch[i] = tmp;
}
}
idx = 1;
traverse(root);
for(idx=1; idx<=N; idx++) if(ans[idx] != inorder[idx]){ printf("NO\n");break;}
if(idx == N + 1) printf("YES\n");
for(int i=1; i<=N; i++) point_to[i] = 0;
}
}
```
:::
---
13157 - Beef color vain
:::spoiler 數學展開，考慮負數
```c=
#include<stdio.h>
#define ma1 100005
#define ma2 1000005
char s[ma2];
int pos=0,arr[ma1],co[ma1];
int getnum(void){
int ret=0;
while('0'<=s[pos]&&s[pos]<='9') ret=ret*10+s[pos++]-'0';
return ret;
}
int build(int p,int q,int coco){
int ret;
if(s[pos]!='f'){
int idx=getnum();
co[idx]=((long long)co[idx]+coco)%q;
ret=((long long)coco*arr[idx])%q;
}
else{
pos+=2;
int l=build(p,q,((long long)coco*p)%q);
pos++;
int r=build(p,q,coco);
pos++;
ret=((long long)l+r)%q;
}
return ret;
}
int main(){
int p,q,n;
scanf("%d %d %d",&p,&q,&n);
for(int i=1;i<=n;i++) scanf("%d",&arr[i]);
scanf("%s",s);
int ans=build(p,q,1),m;
scanf("%d",&m);
while(m--){
int d,v;scanf("%d %d",&d,&v);
ans=((ans+(long long)co[d]*(v-arr[d]))%q+q)%q;
printf("%d\n",ans);
arr[d]=v;
}
}
```
:::
---
---
10993 - Polynomial class
:::spoiler 乘法的處理要注意
```cpp=
#include <iostream>
#include "function.h"
using namespace std;
Polynomial::Polynomial(){}
Polynomial::Polynomial(const int gp, const int cof[51]){
for(int i=gp;i>=0;i--) this->coefficients[i]=cof[i];
this->greatestPower=gp;
}
Polynomial Polynomial::add(Polynomial next) const{
Polynomial tmp=*this;
int gp2=next.greatestPower,gp1=tmp.greatestPower,cnt=gp2>gp1?gp2:gp1;
tmp.greatestPower=cnt;
for(int i=cnt;i>=0;i--) if(i==gp2) tmp.coefficients[i]+=next.coefficients[i],gp2--;
return tmp;
}
Polynomial Polynomial::subtract(const Polynomial next) const{
Polynomial tmp=*this;
int gp2=next.greatestPower,gp1=tmp.greatestPower,cnt=gp2>gp1?gp2:gp1;
tmp.greatestPower=cnt;
for(int i=cnt;i>=0;i--) if(i==gp2) tmp.coefficients[i]-=next.coefficients[i],gp2--;
return tmp;
}
Polynomial Polynomial::multiplication(const Polynomial next) const{
Polynomial tmp=*this;
int gp2=next.greatestPower,gp1=tmp.greatestPower,cnt=gp2+gp1,cotmp[110]={0};
tmp.greatestPower=cnt;
for(int i=0;i<=gp1;i++) for(int j=0;j<=gp2;j++) cotmp[i+j]+=tmp.coefficients[i]*next.coefficients[j];
for(int i=0;i<=cnt;i++) tmp.coefficients[i]=cotmp[i];
return tmp;
}
void Polynomial::output() const{
int i=this->greatestPower;
for(;i>0;i--) cout <<this->coefficients[i]<< " ";
cout<<this->coefficients[0];
}
```
:::
---
10998 - Stack
:::spoiler 除構子要記得寫
```cpp=
#ifndef FUNCTION_H
#define FUNCTION_H
#include <iostream>
#include<stdlib.h>
using namespace std;
class ListNode
{
friend class List_stack; //make List_stack a friend
public:
ListNode( const int &info ) //constructor
: data( info ), nextPtr( NULL ), prevPtr( NULL )
{
} //end ListNode constructor
private:
int data; //data
ListNode *nextPtr; // next node in list
ListNode *prevPtr;
}; //end class ListNode
class List_stack {
public:
List_stack();
~List_stack();
void push(const int &);
void pop();
void print();
private:
ListNode *head;
ListNode *tail;
};
List_stack::List_stack(){
this->head=this->tail=NULL;
}
void List_stack::pop(){
if(this->tail==NULL) return;
ListNode *tmp=this->tail;
this->tail=this->tail->prevPtr;
free(tmp);
}
void List_stack::push(const int &r){
ListNode *tmp=new ListNode(r);
tmp->prevPtr=this->tail;
this->tail=tmp;
}
void List_stack::print(){
ListNode *tmp=this->tail;
while(tmp!=NULL){
if(tmp->prevPtr!=NULL) cout<<tmp->data<<" ";
else cout<<tmp->data;
tmp=tmp->prevPtr;
}
}
#endif // FUNCTION_H
```
:::
---
13178 - Band Ya Rou Ze - Reverse Classtarburst
:::spoiler string處理跟陣列一樣，用swap來排序，使用this指標來操作
```cpp=
#include<iostream>
#include<string>
#include"function.h"
using namespace std;
Node::~Node(){
Node *tmp=neighbors[0];
if(neighbors[0]!=nullptr){neighbors[0]->unLink(this);unLink(neighbors[0]);delete tmp;}
tmp=neighbors[1];
if(neighbors[1]!=nullptr){neighbors[1]->unLink(this);unLink(neighbors[1]);delete tmp;}
}
void List::init(std::string s){
head=new Node(s[0]);
tail=head;
for(int i=1;i<s.length();i++){
Node *tmp=new Node(s[i]);
tail->link(tmp);
tmp->link(tail);
tail=tmp;
}
}
void List::merge(List &front, List &back){
if(front.head==nullptr){head=back.head;tail=back.tail;return;}
if(back.head==nullptr){head=front.head;tail=front.tail;return;}
front.tail->link(back.head);
back.head->link(front.tail);
head=front.head;
tail=back.tail;
}
void List::swap(List &swapList){
std::swap(head,swapList.head);
std::swap(tail,swapList.tail);
}
void List::reverse(){
std::swap(head,tail);
}
List::~List(){
if(head!=nullptr) delete head;
}
```
:::
---
11417 - String Operation
:::spoiler new記得
```cpp=
#include <iostream>
#include "function.h"
using namespace std;
Str::Str(char* input) :head(NULL),tail(NULL){
int idx = 0;
if (input[idx]!='\0'){
Char* temp=new Char(input[idx]);
head=temp,tail=temp,idx++;
while(input[idx]!='\0'){
Char* new_char=new Char(input[idx]);
tail->next=new_char,tail=new_char,idx++;
}
}
}
Str::Str(const Str& copied){
head=new Char(copied.head->text);
tail=head;
Char* temp=copied.head->next;
while(temp!=NULL){
Char* new_char=new Char(temp->text);
tail->next=new_char,tail=new_char,temp=temp->next;
}
}
Str& Str::strInsert(const Str& s){
Str* temp=new Str(s);
this->tail->next=temp->head,this->tail=temp->tail;
return *this;
}
```
:::
---
12753 - Go on mission
:::spoiler 繼承的東西要記得怎麼寫、iomanip
```cpp=
#include <iostream>
#include <string.h>
#include <iomanip>
#include "function.h"
using namespace std;
BigInt::BigInt():sign(true){for (int i = 0; i < N; i++) bigInt[i] = 0;}
BigInt::BigInt(char* input):sign(true){
for (int i = 0; i < N; i++) this->bigInt[i] = 0;
long long len = strlen(input);
int cursor_for_bigInt = 0,i;
for (i = len - 1; i > 7; i -= 8) {
int temp = 0;
for (int j = i - 7; j <= i; j++) {temp *= 10;temp += input[j] - '0';}
this->bigInt[cursor_for_bigInt++] = temp;
}
int temp = 0;
for (int j = 0; j <= i; j++) {temp *= 10;temp += input[j] - '0';}
this->bigInt[cursor_for_bigInt] = temp;
}
BigInt::BigInt(const BigInt& copid){*this = copid;}
BigInt& BigInt::operator = (const BigInt& copid){
if (this == &copid) return *this;
this->sign = copid.sign;
for (int i = 0; i < N; i++) this->bigInt[i] = copid.bigInt[i];
return *this;
}
bool BigInt::operator < (BigInt right){
if (this->sign == true && right.sign == false) return false;
else if (this->sign == false && right.sign == true) return true;
else if (this->sign == true && right.sign == true) {
for (int i = N - 1; i >= 0; i--) {
if (this->bigInt[i] > right.bigInt[i]) return false;
else if (this->bigInt[i] < right.bigInt[i]) return true;
}
}
else if (this->sign == false && right.sign == false) {
for (int i = N - 1; i >= 0; i--) {
if (this->bigInt[i] > right.bigInt[i]) return true;
else if (this->bigInt[i] < right.bigInt[i]) return false;
}
}
return false;
}
bool BigInt::operator > (BigInt right){
if (this->sign == true && right.sign == false) return true;
else if (this->sign == false && right.sign == true) return false;
else if (this->sign == true && right.sign == true) {
for (int i = N - 1; i >= 0; i--) {
if (this->bigInt[i] > right.bigInt[i]) return true;
else if (this->bigInt[i] < right.bigInt[i]) return false;
}
}
else if (this->sign == false && right.sign == false) {
for (int i = N - 1; i >= 0; i--) {
if (this->bigInt[i] > right.bigInt[i]) return false;
else if (this->bigInt[i] < right.bigInt[i]) return true;
}
}
return false;
}
bool BigInt::operator == (BigInt right){
if (this->sign != right.sign) return false;
for (int i = N - 1; i >= 0; i--) if (this->bigInt[i] != right.bigInt[i]) return false;
return true;
}
bool BigInt::operator >= (BigInt right){
if (this->sign == true && right.sign == false) return true;
else if (this->sign == false && right.sign == true) return false;
else if (this->sign == true && right.sign == true) {
for (int i = N - 1; i >= 0; i--) {
if (this->bigInt[i] > right.bigInt[i]) return true;
else if (this->bigInt[i] < right.bigInt[i]) return false;
}
}
else if (this->sign == false && right.sign == false) {
for (int i = N - 1; i >= 0; i--) {
if (this->bigInt[i] > right.bigInt[i]) return false;
else if (this->bigInt[i] < right.bigInt[i]) return true;
}
}
return true;
}
bool BigInt::operator <= (BigInt right){
if (this->sign == true && right.sign == false) return false;
else if (this->sign == false && right.sign == true) return true;
else if (this->sign == true && right.sign == true) {
for (int i = N - 1; i >= 0; i--) {
if (this->bigInt[i] > right.bigInt[i]) return false;
else if (this->bigInt[i] < right.bigInt[i]) return true;
}
}
else if (this->sign == false && right.sign == false) {
for (int i = N - 1; i >= 0; i--) {
if (this->bigInt[i] > right.bigInt[i]) return true;
else if (this->bigInt[i] < right.bigInt[i]) return false;
}
}
return true;
}
BigInt BigInt::operator + (BigInt right) {return *this;}
BigInt BigInt::operator - (BigInt right){
BigInt ans;
if (this->sign == true) {
if (*this == right) {
ans.sign = true;
for (int i = 0; i < N; i++) ans.bigInt[i] = 0;
}
else if (*this > right) {
ans.sign = true;
for (int i = 0; i < N; i++) {
if (this->bigInt[i] > right.bigInt[i]) ans.bigInt[i] = this->bigInt[i] - right.bigInt[i];
else if (this->bigInt[i] < right.bigInt[i]) {this->bigInt[i + 1] -= 1;ans.bigInt[i] = this->bigInt[i] + (BASE - right.bigInt[i]);}
else ans.bigInt[i] = 0;
}
}
else if (*this < right) {
ans.sign = false;
for (int i = 0; i < N; i++) {
if (right.bigInt[i] > this->bigInt[i])ans.bigInt[i] = right.bigInt[i] - this->bigInt[i];
else if (right.bigInt[i] < this->bigInt[i]) {right.bigInt[i + 1] -= 1;ans.bigInt[i] = right.bigInt[i] + (BASE - this->bigInt[i]);}
else ans.bigInt[i] = 0;
}
}
}
else if (this->sign == false) {
ans.sign = false;
for (int i = 0; i < N; i++) {
ans.bigInt[i] = this->bigInt[i] + right.bigInt[i];
if (ans.bigInt[i] >= BASE) {ans.bigInt[i] = ans.bigInt[i] - BASE;this->bigInt[i + 1] += 1;}
}
}
return ans;
}
istream& operator >> (istream& in, BigInt& n){
char str[1205]; cin >> str;
n = BigInt(str);
return in;
}
ostream& operator << (ostream& out, BigInt& n){
if (n.sign == false) cout << "-";
bool start = false,first = true;
for (int i = 149; i >= 0; i--) {
if (n.bigInt[i] != 0) start = true;
if (start) {
if (first) {cout << n.bigInt[i];first = false;}
else cout << setw(8) << setfill('0') << n.bigInt[i];
}
}
if (!start) cout << "0";
return out;
}
void solution(BigInt& tanjiro, BigInt& zenitsu, BigInt& inosuke, int n) {
for (int i = 0; i < n; i++) {
BigInt mission;cin >> mission;
if (inosuke >= tanjiro && inosuke >= zenitsu) inosuke = inosuke - mission;
else if (tanjiro >= inosuke && tanjiro >= zenitsu) tanjiro = tanjiro - mission;
else if (zenitsu >= inosuke && zenitsu >= tanjiro) zenitsu = zenitsu - mission;
}
}
```
:::
---
13199 - Vector Implementation
:::spoiler new,delete要寫對(delete[] arr_)、insert()要寫對(沒那麼簡單)、有些function可以用reserve實作
```cpp=
#include"function.h"
#include <cstdint>
using namespace oj;
Vector::Vector():cap_(0),size_(0),arr_(nullptr){};
Vector::Vector(const Vector &rhs){
size_=rhs.size_,cap_=rhs.cap_;arr_=new value_type*[cap_];
for(int i=0;i<cap_;i++) {if(i<size_) arr_[i]=new value_type(*(rhs.arr_[i]));else arr_[i]=nullptr;}
}
Vector& Vector::operator=(const Vector &rhs){
for(int i=0;i<size_;i++) delete arr_[i];
delete [] arr_;
size_=rhs.size_,cap_=rhs.cap_;arr_=new value_type*[cap_];
for(int i=0;i<cap_;i++) {if(i<size_) arr_[i]=new value_type(*(rhs.arr_[i]));else arr_[i]=nullptr;}
return *this;
}
reference Vector::front(){
return *(arr_[0]);
}
reference Vector::back(){
return *(arr_[size_-1]);
}
reference Vector::operator[](size_type pos){
return *(arr_[pos]);
}
const_reference Vector::operator[](size_type pos) const{
return *(arr_[pos]);
}
size_type Vector::capacity() const{return cap_;}
size_type Vector::size() const{return size_;}
void Vector::clear(){
for(int i=0;i<size_;i++) delete arr_[i];
size_=0;
}
bool Vector::empty()const{
if(size_==0) return true;
else return false;
}
void Vector::erase(size_type pos){
delete arr_[pos];
for(int i=pos;i<size_-1;i++) arr_[i]=arr_[i+1];
arr_[size_-1]=nullptr;
size_--;
}
void Vector::insert(size_type pos, size_type cnt, const_reference val){
int int_cap=1;if(cap_==0) cap_=1;
while(cnt+size_>cap_*int_cap) int_cap*=2;
reserve(cap_*int_cap);size_+=cnt;
for(int i=size_-1;i>=pos;i--){
if(i>=pos+cnt) arr_[i]=arr_[i-cnt];
else{
arr_[i]=new value_type(val);
if(i==0) break;
}
}
}
void Vector::pop_back(){
delete arr_[--size_];
}
void Vector::pop_front(){
delete arr_[0];
for(int i=0;i<size_-1;i++) arr_[i]=arr_[i+1];
arr_[size_-1]=nullptr;
size_-=1;
}
void Vector::push_back(const_reference val){
if(size_==cap_) reserve(cap_+1);
arr_[size_++]=new value_type(val);
}
void Vector::push_front(const_reference val){
if(size_==cap_) reserve(cap_+1);
for(int i=size_;i>=1;i--) arr_[i]=arr_[i-1];
arr_[0]=new value_type(val);
size_++;
}
void Vector::reserve(size_type new_capacity){
if(cap_>=new_capacity) return;
value_type **tmp=new value_type*[new_capacity];
for(int i=0;i<new_capacity;i++) tmp[i]=(i<size_)?arr_[i]:nullptr;
delete [] arr_;
arr_=tmp;
cap_=new_capacity;
}
void Vector::shrink_to_fit(){
if(cap_==size_) return;
value_type **tmp=new value_type*[size_];
for(int i=0;i<size_;i++) tmp[i]=arr_[i];
delete [] arr_;
arr_=tmp;
cap_=size_;
}
Vector::~Vector(){
for(int i=0;i<size_;i++) delete arr_[i];
delete [] arr_;
}
```
:::
---
11021 - Encoding and decoding
:::spoiler 用sring寫就好，不用用stringstream寫，decode()那邊要注意
```cpp=
#include "function.h"
void RleCodec::encode(){
std::string s = "";
char c = ' '; //c 同樣的字
int num = 0;
code_str += ' '; //要處理最後一組
for(char u:code_str){
if(u==c || num==0) num++, c = u; //num < 'A' 處理最開始
else{
while(num>=26) s = s + "QZ" + c, num -= 26;
if(num) s = s + 'Q' + char('A'+num-1) + c;
num = 1, c = u;
}
}
code_str = s, encoded = true;
}
void RleCodec::decode(){
std::string s = "";
int num = 0, ok = 0;
for(char u:code_str){
if(!ok) ok = 1;
else if(num){
while(num) s += u, num--;
ok = 0;
}
else num = u-'A'+1;
}
code_str = s, encoded = false;
}
```
```cpp=
#include<sstream>
#include"function.h" //WA_code,but don't know why
using namespace std;
void RleCodec::encode(){
stringstream ss;
int count=0;
char tmp=code_str[0];
for(int i=0;code_str[i]!='\0';i++){
if(tmp==code_str[i]) count++;
else{
while(count>26){ss<<"Q"<<"Z"<<tmp;count-=26;}
ss<<"Q"<<(char)('A'+count-1)<<tmp;
tmp=code_str[i],count=1;
}
}
//ss<<"Q"<<(char)('A'+count-1)<<tmp;
code_str=ss.str();
encoded=true;
}
void RleCodec::decode(){
stringstream ss;
bool is_headQ=true,is_numC=false;
int count=0;
for(int i=0;code_str[i]!='\0';i++){
if(is_headQ) {is_headQ=false,is_numC=true;continue;}
else if(is_numC){count=code_str[i]-'A';is_numC=false;continue;}
else{
for(int j=0;j<count;j++) ss<<code_str[i];
is_headQ=true;continue;
}
}
code_str=ss.str();
encoded=false;
}
```
:::
---
12224 - Doubly Linked List
:::spoiler 基本上都是重點啦，細節
```cpp=
#include"function.h"
void List::InsertHead(int data) {
ListNode* newHead = new ListNode;
newHead->data = data,newHead->next = head,newHead->prev = nullptr;
if (head != nullptr) head->prev = newHead;
if (cnt == 0) {
middle = newHead,tail = newHead,head = newHead,cnt++,pos++;
return;
}
head = newHead,cnt++,pos++;
if (cnt / 2 + 1 < pos) pos--,middle = middle->prev;
}
int List::RemoveHead() {
if (head == nullptr) throw std::out_of_range("\n");
cnt--,pos--;
if (cnt / 2 + 1 < pos) pos--,middle = middle->prev;
ListNode* oldHead = head;
int oldData = oldHead->data;
head = head->next;
if (head != nullptr) head->prev = nullptr;
delete oldHead;
if (cnt == 0) reset();
return oldData;
}
void List::InsertTail(int data) {
ListNode* newTail = new ListNode;
newTail->data = data;
newTail->next = nullptr;
newTail->prev = tail;
if (tail != nullptr) tail->next = newTail;
if (cnt == 0) {
head = newTail,middle = newTail,tail = newTail,cnt++,pos++;
return;
}
tail = newTail,cnt++;
if (cnt / 2 + 1 > pos) pos++,middle = middle->next;
}
int List::RemoveTail() {
if (tail == nullptr) throw std::out_of_range("\n");
cnt--;
if (cnt / 2 + 1 < pos) pos--,middle = middle->prev;
ListNode* oldTail = tail;
int oldData = oldTail->data;
tail = tail->prev;
if (tail != nullptr) tail->next = nullptr;
delete oldTail;
if (cnt == 0) reset();
return oldData;
}
void List::Swap() {
if (cnt == 0 || cnt == 1) return;
ListNode *oldHead = head,*oldTail = tail,*oldMiddle = middle;
head = oldMiddle,tail = oldMiddle->prev;
oldTail->next = oldHead,oldHead->prev = oldTail;
head->prev = nullptr,tail->next = nullptr;
if (cnt % 2 == 0) pos--;
middle = oldTail;
if (cnt / 2 + 1 > pos) pos++,middle = middle->next;
}
```
:::
---
12257 - Only children make choice!
:::spoiler Diamond_inheritance在幹嘛很重要
```cpp=
#include"function.h"
void Caog::barking(){cout<< "woof!woof!meow!\n";}
void Caog::carton(){cout<< "it looks so happy!\n";}
void Caog::throwBall(){cout<< "it looks happy!\n";}
Animal::Animal(Zoo *zoo, string name){zoo->born(name),belong=zoo,species=name;}
Dog::Dog(Zoo *zoo):Animal(zoo,"Dog"){}
Dog::~Dog(){}
Cat::Cat(Zoo *zoo):Animal(zoo,"Cat"){}
Cat::~Cat(){}
Caog::Caog(Zoo *zoo):Animal(zoo,"Caog"),Dog(zoo),Cat(zoo){}
Caog::~Caog(){}
```
:::
---
13205 - Happy Ball
:::spoiler 各種細節操作要記得
```cpp=
#include"function.h"
ContainerBase* create(int n,int* arr,int q,Operation* pos){
int po2cnt=0,po3cnt=0;
for(int i=1;i<=q;i++){
if(pos[i].type==2) po2cnt++;
if(pos[i].type==3) po3cnt++;
}
return (po2cnt>po3cnt?(ContainerBase*)new Array(n,arr):(ContainerBase*)new List(n,arr));
}
void Array::move(int delta){
cur+=delta; //'+='!!!
if(cur>size) cur=size;
else if(cur<1) cur=1;
}
void Array::remove(){
for(int i=cur;i<size;i++) mem[i]=mem[i+1];
size--;if(cur==size+1) cur--;
}
void List::move(int delta){
if(delta>0) for(int i=0;i<delta;i++){if(cur->getNxt()==nullptr) break;cur=cur->getNxt();}
else if(delta<0) for(int i=delta;i<0;i++){if(cur->getPre()==nullptr) break;cur=cur->getPre();}
}
void List::remove(){
cur=cur->remove();size--;
}
```
:::
Sign in with Wallet
Connect another wallet