note.ms/meowjiao 备份
meowjiaoの云记事板
2023.12.9
int search(int k) {
for (int i = 1;i <= 算法总数;i++) {
if (满足条件) {
保存结果;
if (到目的地) {
输出解;
}
else {
search(k + 1);
}
恢复: 保存结果之前状态, 回溯一步
}
}
}
int search(int k) {
if (到目的地) {
输出解;
}
else {
for (int i = 1;i <= 算法总数;i++) {
if (满足条件) {
保存结果;
search(k + 1);
恢复: 保存结果之前状态, 回溯一步
}
}
}
}
2023.12.16
有序(非降序)
lower_bound(first,last,val)
找到第一个大于或等于val的元素，并返回该元素的地址，若不存在，返回last
降序
小于或等于 lower_bound(first,last,val,cmp)
有序(非降序)
upper_bound(first,last,val)
第一个大于val的值，并返回该元素的地址，若不存在，返回last
有序(降序)
upper_bound(first,last,val,greater<>())
第一个小于val的值，并返回该元素的地址，若不存在，返回last
x ^ n = n * (x ^ n - 1)
2023.12.23
https://noi.openjudge.cn
1.11 2.4 2.5 寒假前最后一节课前做完（寒假2024/01/20）
---
所有stl容器都是左闭右开的（stl.begin()是第一个元素的迭代器，stl.end()是最后一个元素的后一个“元素”的迭代器）
---
vector:
v.insert(位置，值)
v.clear()也删空间
---
set:
set反向遍历 for(set<类型>::iterator it = s.rbegin();it != s.rend();it++)
s.erase(要删的数)，不用传迭代器
s.find(要找的数)，找到返回迭代器，找不到返回s.end()
---
struct:
stl存struct 访问struct成员: (*it).成员名 一定加括号，因为.的优先级比*高
struct重载小于号
struct info {
string name;
double score;
bool operator < (const info &a) const {
return a.score < score; // 从大到小排序
}
};
---
~~2023/12/23 14:17 银座京都国际旁边高架桥上一辆救护车驶过~~
---
multiset:
multiset <类型> 容器名;
包含set的所有操作，但是不去重，因此有别的函数
ms.count(要查询的数字); 找这个数字有几个
---
~~财，就多敛~~
---
王老师QQ号233836613
---
作业：luogu P1162 P1443
---
luogu P1162:
#include<bits/stdc++.h>
using namespace std;
int xx[]={0,-1,0,1};
int yy[]={1,0,-1,0};
int mp[35][35];
bool vis[35][35];
int n;
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
cin>>mp[i][j];
queue <int> x;
queue <int> y;
//把起点入队
x.push(0);
y.push(0);
vis[0][0]=1;
//广搜
while(!x.empty()){
//int tx=x.front();
//int ty=y.front();
for(int i=0;i<4;i++){
int nx=x.front()+xx[i];
int ny=y.front()+yy[i];
if(nx>=0&&nx<=n+1 && ny>=0&&ny<=n+1 && mp[nx][ny]==0 && vis[nx][ny]==0){
x.push(nx);
y.push(ny);
vis[nx][ny]=1;
}
}
x.pop();
y.pop();
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(mp[i][j]==0 && vis[i][j]==0)
cout<<2<<" ";
else
cout<<mp[i][j]<<" ";
}
cout<<endl;
}
return 0;
}
---
luogu P1080:
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <cstring>
#include <vector>
#include <cmath>
#include <queue>
#include <stack>
#include <set>
#include <climits>
using namespace std;
int n,a,b;
int ans[4005],s[4005],ls=1,lans;
struct dc{
int x,y;
}c[1010];
bool cmp(dc e,dc f){
return e.x*e.y<f.x*f.y;
}
void f(int t){
//ans=max(ans,s/c[i].y);
int d[4005]={0},ld=ls;
for(int i=ls;i>=1;i--){
d[i]+=s[i];
d[i-1]+=d[i]%t*10;
d[i]/=t;
}
while(d[ld]==0&&ld>1)
ld--;
int flag=0;
if(lans<ld)
flag=1;
else if(lans>ld)
flag=0;
else{
for(int i=ld;i>=1;i--){
if(ans[i]>d[i]){
flag=0;
break;
}
if(ans[i]<d[i]){
flag=1;
break;
}
}
}
if(flag){
lans=ld;
for(int i=1;i<=ld;i++)
ans[i]=d[i];
}
}
int main(){
cin>>n>>s[1]>>b;
for(int i=1;i<=n;i++)
cin>>c[i].x>>c[i].y;
sort(c+1,c+n+1,cmp);
for(int i=1;i<=n;i++){
f(c[i].y);
for(int j=1;j<=ls;j++)
s[j]*=c[i].x;
for(int j=1;j<=ls;j++){
s[j+1]+=s[j]/10;
s[j]%=10;
if(s[ls+1]>0)
ls++;
}
}
for(int i=lans;i>=1;i--)
cout<<ans[i];
return 0;
}
---
luogu P1141 P1135 P1032 P1126 P3956
顺序1141 -> 1032 -> 1126 -> 3956 -> 1135
---
luogu P1141 并查集:
#include<iostream>
using namespace std;
int n,m;
struct node{
int id;
int num;
}f[2000086];
int dx[]={1,0,-1,0};
int dy[]={0,1,0,-1};
char c[1006][1006];
int v[1005][1005];
int find(int x){
if(f[x].id==x){
return x;
}
return f[x].id=find(f[x].id);
}
void merge(int a,int b){
f[find(f[b].id)].id=f[find(f[a].id)].id;
f[find(f[a].id)].num+=1;
}
void dfs(int x,int y){
v[x][y]=1;
for(int i=0;i<4;i++){
int fx=dx[i]+x;
int fy=dy[i]+y;
if(fx>=1&&fx<=n&&fy>=1&&fy<=n&&c[fx][fy]!=c[x][y]&&!v[fx][fy]){
merge(x*n+y,fx*n+fy);
dfs(fx,fy);
}
}
}
int main(){
cin>>n>>m;
for(int i=1;i<=2000005;i++){
f[i].id=i;
f[i].num=1;
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
cin>>c[i][j];
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(!v[i][j]){
dfs(i,j);
}
}
}
for(int i=0;i<m;i++){
int x,y;
cin>>x>>y;
cout<<f[find(x*n+y)].num<<endl;
}
return 0;
}
---
luogu P1141不用color方法:
#include<bits/stdc++.h>
using namespace std;
int n,m,mp[1010][1010],vis[1010][1010],dx[]={0,1,0,-1},dy[]={1,0,-1,0};
char s[1010][1010];
struct node{
int x,y;
};
int main(){
scanf("%d %d ",&n,&m);
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++){
scanf("%c ",&s[i][j]);
mp[i][j]=-1;
}
while(m--){
int x,y;
scanf("%d %d",&x,&y);
if(mp[x][y]!=-1){
printf("%d\n",mp[x][y]);
continue;
}
queue<node> q;
queue<node> q1;
mp[x][y]=1;
node cn;
cn.x=x,cn.y=y;
q.push(cn);
q1.push(cn);
int cnt=1;
while(!q.empty()){
int nx=q.front().x,ny=q.front().y;
vis[nx][ny]=1;
q.pop();
for(int i=0;i<4;i++){
int xx=nx+dx[i],yy=ny+dy[i];
if(xx>=1&&yy>=1&&xx<=n&&yy<=n&&s[nx][ny]!=s[xx][yy]&&!vis[xx][yy]){
vis[xx][yy]=1;
node cn1;
cn1.x=xx,cn1.y=yy;
q.push(cn1);
q1.push(cn1);
cnt++;
}
}w
}
printf("%d\n",cnt);
while(!q1.empty()){
int nx=q1.front().x,ny=q1.front().y;
mp[nx][ny]=cnt;
// printf("%d %d\n",nx,ny);
q1.pop();
}
}
return 0;
}
---
http://noi.openjudge.cn/ch0205/1817 判断和里有没有1 2 4 8
1.与
n & 1 -> 是否有1
n & 2 -> 是否有2
n & 4 -> 是否有4
n & 8 -> 是否有8
2.右移 + 与
n >> 0 & 1 -> 是否有1
n >> 1 & 1 -> 是否有2
n >> 2 & 1 -> 是否有4
n >> 3 & 1 -> 是否有8
---
http://noi.openjudge.cn/ch0205/1817 代码
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <cstring>
#include <vector>
#include <cmath>
#include <queue>
#include <stack>
#include <set>
#include <climits>
#include <map>
using namespace std;
typedef pair <int,int> PII;
const int N=55;
int g[N][N],n,m;
bool vis[N][N];
int xx[]={0,-1,0,1};
int yy[]={-1,0,1,0};
int bfs(int x,int y){
queue <PII> que;
que.push({x,y});
vis[x][y]=1;
int cnt=0;
while(!que.empty()){
PII f=que.front();
que.pop();
cnt++;
int x=f.first;
int y=f.second;
for(int i=0;i<4;i++){
if(!(g[x][y]>>i&1)){
int nx=x+xx[i];
int ny=y+yy[i];
if(vis[nx][ny]==0){
que.push({nx,ny});
vis[nx][ny]=1;
}
}
}
}
return cnt;
}
int main(){
cin>>n>>m;
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
cin>>g[i][j];
int res=0,maxv=0;
for(int i=0;i<n;i++)
for(int j=0;j<m;j++){
if(vis[i][j]==0){
res++;
maxv=max(maxv,bfs(i,j));
}
}
cout<<res<<endl<<maxv;
return 0;
}
---
#include <iostream>
#include <cstring>
#include <cmath>
#include <queue>
using namespace std;
struct node {
int x,y,dis;
bool idk,flag[10];
};
int r,c,k,cnt,doors[20][2],fx[] = {0,-1,1,0,0},fy[] = {0,0,0,-1,1};
bool vis[210][210][40];
char a[210][210];
node s,door;
queue<node> q;
int main() {
int t;
cin >> t;
while (t--) {
cin >> r >> c >> k;
for (int i = 1;i <= r;i++) {
for (int j = 1;j <= c;j++) {
cin >> a[i][j];
if (a[i][j] == 'S') {
s.x = i;
s.y = j;
s.dis = 0;
s.idk = true;
memset(s.flag,0,sizeof(s.flag));
}
else if (a[i][j] == '$') {
doors[++cnt][0] = i;
doors[cnt][1] = j;
}
}
}
bool find = false;
q.push(s);
while (!q.empty()) {
s = q.front();
q.pop();
if (find) {
break;
}
for (int i = 1;i <= 4;i++) {
node t = s;
t.x += fx[i];
t.y += fy[i];
t.dis++;
if (t.x < 1 || t.x > r || t.y < 0 || t.y > c || a[t.x][t.y] == '#') {
continue;
}
if (a[t.x][t.y] >= '0' && a[t.x][t.y] <= '4') {
t.flag[a[t.x][t.y] - '0'] = true;
}
int idk_cnt = 0,wssb = 0;
for (int i = 1;i <= 5;i++) {
if (t.flag[i]) {
wssb += pow(2,i - 1);
idk_cnt++;
}
}
if (vis[t.x][t.y][wssb]) {
continue;
}
vis[t.x][t.y][wssb] = true;
if (idk_cnt >= k) {
t.idk = false;
}
if (a[t.x][t.y] == '$') {
door = t;
for (int i = 1;i <= cnt;i++) {
if ((doors[i][0] != t.x) && (doors[i][1] != t.y)) {
door.x = doors[i][0];
door.y = doors[i][1];
q.push(door);
}
}
}
if (a[t.x][t.y] == 'E' && !t.idk) {
cout << t.dis << '\n';
find = true;
}
}
}
if (!find) {
cout << "oop!\n";
}
}
return 0;
}
---
P1118 P1434 P1433 P1784 P1074
---
P1784 TLE代码
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <cstring>
#include <vector>
#include <cmath>
#include <queue>
#include <stack>
#include <climits>
using namespace std;
int mp[10][10],vx[10][10],vy[10][10],vc[10][10];
void dfs(int x,int y){
if(x==9){
for(int i=0;i<9;i++){
for(int j=0;j<9;j++)
cout<<mp[i][j]<<" ";
cout<<endl;
}
return ;
}
if(y==9){
dfs(x+1,0);
return ;
}
if(mp[x][y])
dfs(x,y+1);
else
for(int i=1;i<=9;i++){
if(!vx[x][i]&&!vy[y][i]&&!vc[x/3*3+y/3][i]){
vx[x][i]=1;
vy[y][i]=1;
vc[x/3*3+y/3][i]=1;
mp[x][y]=i;
dfs(x,y+1);
vx[x][i]=0;
vy[y][i]=0;
vc[x/3*3+y/3][i]=0;
mp[x][y]=0;
}
}
}
int main(){
for(int i=0;i<9;i++){
for(int j=0;j<9;j++){
cin>>mp[i][j];
vx[i][mp[i][j]]=1;
vy[j][mp[i][j]]=1;
vc[i/3*3+j/3][mp[i][j]]=1;
}
}
dfs(0,0);
return 0;
}
---
#include <iostream>
using namespace std;
int a[10][10];
bool h[10][10],l[10][10],g[10][10];
void dfs(int x,int y) {
if (a[x][y]) {
if (x == 9 && y == 9) {
for (int i = 1;i <= 9;i++) {
for (int j = 1;j <= 9;j++) {
cout << a[i][j] << ' ';
}
cout << '\n';
}
exit(0);
}
else if (y == 9) {
dfs(x + 1,1);
}
else {
dfs(x,y + 1);
}
}
else {
for (int i = 1;i <= 9;i++) {
if (!h[x][i] && !l[y][i] && !g[1 + (x - 1) / 3 * 3 + (y - 1) / 3][i]) {
h[x][i] = l[y][i] = g[1 + (x - 1) / 3 * 3 + (y - 1) / 3][i] = true;
a[x][y] = i;
if (x == 9 && y == 9) {
for (int j = 1;j <= 9;j++) {
for (int k = 1;k <= 9;k++) {
cout << a[j][k] << ' ';
}
cout << '\n';
}
exit(0);
}
else if (y == 9) {
dfs(x + 1,1);
}
else {
dfs(x,y + 1);
}
h[x][i] = l[y][i] = g[1 + (x - 1) / 3 * 3 + (y - 1) / 3][i] = false;
a[x][y] = 0;
}
}
}
}
int main() {
for (int i = 1;i <= 9;i++) {
for (int j = 1;j <= 9;j++) {
int t;
cin >> t;
if (t) {
h[i][t] = l[j][t] = g[1 + (i - 1) / 3 * 3 + (j - 1) / 3][t] = true;
a[i][j] = t;
}
}
}
dfs(1,1);
return 0;
}
---
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <cstring>
#include <vector>
#include <cmath>
#include <queue>
#include <stack>
#include <climits>
using namespace std;
int n,m,sx,sy,tx,ty,p,fx;
char f;
bool mp[55][55],vis[55][55][4];
int xx[]={-1,0,1,0};
int yy[]={0,1,0,-1};
struct robot{
int x,y,s,d;
};
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++){
cin>>p;
if(p==1)
mp[i][j]=mp[i-1][j]=mp[i][j-1]=mp[i-1][j-1]=1;
}
cin>>sx>>sy>>tx>>ty>>f;
if(f=='N')
fx=0;
if(f=='E')
fx=1;
if(f=='S')
fx=2;
if(f=='W')
fx=3;
queue <robot> q;
q.push({sx,sy,0,fx});
while(!q.empty()){
robot t1=q.front();
vis[t1.x][t1.y][t1.d]=1;
if(t1.x==tx&&t1.y==ty){
cout<<t1.s;
return 0;
}
robot t=t1;
t.s++;
t.d=(t.d+1)%4;
if(!vis[t.x][t.y][t.d])
q.push(t);
t.d=(t.d+2)%4;
if(!vis[t.x][t.y][t.d])
q.push(t);
t.d=t1.d;
t.x+=xx[t.d];
t.y+=yy[t.d];
if(t.x>=1&&t.x<n&&t.y>=1&&t.y<m&&!vis[t.x][t.y][t.d]&&!mp[t.x][t.y]){
q.push(t);
t.x+=xx[t.d];
t.y+=yy[t.d];
if(t.x>=1&&t.x<n&&t.y>=1&&t.y<m&&!vis[t.x][t.y][t.d]&&!mp[t.x][t.y]){
q.push(t);
t.x+=xx[t.d];
t.y+=yy[t.d];
if(t.x>=1&&t.x<n&&t.y>=1&&t.y<m&&!vis[t.x][t.y][t.d]&&!mp[t.x][t.y])
q.push(t);
}
}
q.pop();
}
cout<<-1;
return 0;
}
---
P1092 90pts code
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <cstring>
#include <vector>
#include <cmath>
#include <queue>
#include <stack>
#include <climits>
using namespace std;
int n,a[30],c[4][30],v[30];
void dfs(int x,int y,int t){
if(y>n){
if(t==0)
for(int i=0;i<n;i++)
cout<<a[i]<<" ";
return ;
}
int z=c[x][y];
if(x<=2){
if(a[z]!=-1)
dfs(x+1,y,t);
else{
for(int i=0;i<n;i++){
if(!v[i]){
v[i]=1;
a[z]=i;
dfs(x+1,y,t);
v[i]=0;
a[z]=-1;
}
}
}
}
else{
t+=a[c[1][y]]+a[c[2][y]];
if(a[z]==t%n)
dfs(1,y+1,t/n);
if(a[z]==-1&&v[t%n]==0){
a[z]=t%n;
v[t%n]=1;
dfs(1,y+1,t/n);
a[z]=-1;
v[t%n]=0;
}
}
}
int main(){
memset(a,-1,sizeof(a));
cin>>n;
for(int i=1;i<=3;i++){
for(int j=n;j>=1;j--){
char t;
cin>>t;
c[i][j]=t-'A';
}
}
dfs(1,1,0);
return 0;
}
---
P1092 90pts code
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <cstring>
#include <vector>
#include <cmath>
#include <queue>
#include <stack>
#include <climits>
using namespace std;
int n,a[30],c[4][30],v[30];
void dfs(int x,int y,int t){
if(y>n){
if(t==0)
for(int i=0;i<n;i++)
cout<<a[i]<<" ";
return ;
}
int z=c[x][y];
if(x<=2){
if(a[z]!=-1)
dfs(x+1,y,t);
else{
for(int i=0;i<n;i++){
if(!v[i]){
v[i]=1;
a[z]=i;
dfs(x+1,y,t);
v[i]=0;
a[z]=-1;
}
}
}
}
else{
t+=a[c[1][y]]+a[c[2][y]];
if(a[z]==t%n)
dfs(1,y+1,t/n);
if(a[z]==-1&&v[t%n]==0){
a[z]=t%n;
v[t%n]=1;
dfs(1,y+1,t/n);
a[z]=-1;
v[t%n]=0;
}
}
}
int main(){
memset(a,-1,sizeof(a));
cin>>n;
for(int i=1;i<=3;i++){
for(int j=n;j>=1;j--){
char t;
cin>>t;
c[i][j]=t-'A';
}
}
dfs(1,1,0);
return 0;
}
2025/3/1
https://lgfriends.us.kg/INFO