2024.4.12 【“相遇总是猝不及防、爱意总是野蛮生长”】
Sunday 三月初四
<theme = oi-"search">
P1092 NOIP2004 提高组 虫食算
//2024.4.12
//by white_ice
#include<bits/stdc++.h>
using namespace std;
#define itn int
const int oo = 30;
char s1[oo],s2[oo],s3[oo];
itn st1[oo],st2[oo],st3[oo];
int n;
itn nxt[oo],cnt;
bool used[oo];
int out[oo];
void check(){
int p = 0;
for (itn i=n-1;i>=0;i--){
int a = out[st1[i]];
int b = out[st2[i]];
int c = out[st3[i]];
if ((a+b+p)%n!=c)
return ;
p = (a+b+p)/n;
}
for (itn i=0;i<n;i++)
cout << out[i] << ' ';
exit(0);
}
void dfs(itn x){
if (out[st1[0]]+out[st2[0]]>=n)
return ;
for (int i=n-1;i>=0;i--){
int a = out[st1[i]];
int b = out[st2[i]];
itn c = out[st3[i]];
if (a==-1||b==-1||c==-1)
continue;
if ((a+b)%n!=c&&(a+b+1)%n!=c)
return ;
}
if (x==n){
check();
return ;
}
for (int i=n-1;i>=0;i--){
if (!used[i]){
out[nxt[x]] = i;
used[i] = 1;
dfs(x+1);
used[i] = 0;
out[nxt[x]] = -1;
}
}
return ;
}
void get(itn x){
if (!used[x])used[x] = 1,nxt[cnt++] = x;
return ;
}
int main(){
cin >>n;
scanf("%s%s%s",s1,s2,s3);
for (itn i=0;i<n;i++){
st1[i] = s1[i]-'A';
st2[i] = s2[i]-'A';
st3[i] = s3[i]-'A';
out[i] = -1;
}
for (int i=n-1;i>=0;i--)
get(st1[i]),get(st2[i]),get(st3[i]);
for (itn i=0;i<n;i++)
used[i] = 0;
dfs(0);
return 0;
}
P5691 NOI2001 方程的解数
//2024.4.12
//by white_ice
#include<bits/stdc++.h>
using namespace std;
#define itn int
const int oo = 150;
int n,m;
itn p[10],k[10];
int a[4000006],b[4000006];
int bjwd(int a,int b,int t=1){for(;b;b>>=1,a=a*a)if(b&1)t=t*a;return t;}
//qpow
void dfs(itn l,itn r,int sum,itn *arr,int &cnt){
if (l>r){
arr[++cnt] = sum;
return ;
}
for (itn i=1;i<=m;i++)
dfs(l+1,r,sum+k[l]*bjwd(i,p[l]),arr,cnt);
}
itn cnta,cntb;
int ans;
int main(){
cin >> n >> m ;
for (itn i=1;i<=n;i++)
cin >>k[i] >> p[i];
int mid = (1+n)>>1;
dfs(1,mid,0,a,cnta);
dfs(mid+1,n,0,b,cntb);
sort(a+1,a+1+cnta);
sort(b+1,b+1+cntb);
int l = 1,r = cntb;
for (;l<=cnta&&r>=1;l++){
while (a[l]+b[r]>0)
r--;
itn x = 1,y = 0;
for (itn j=r;a[l]+b[j]==0&&j>0;j--)
y++;
while (l<cnta&&a[l]==a[l+1])
x++,l++;
ans+=x*y;
}
cout << ans;
return 0;
}
P3956 NOIP2017 普及组 棋盘
//2024.4.12
//by white_ice
#include<bits/stdc++.h>
using namespace std;
#define itn int
const int inf = 0x3f3f3f3f;
const int oo = 102;
const int dx[] = {0,1,0,-1,1,1,-1,-1,0,2,0,-2};
const int dy[] = {1,0,-1,0,1,-1,1,-1,2,0,-2,0};
const int dw[] = {0,0,0,0,2,2,2,2,2,2,2,2};
struct nod{itn x,y,c,w;bool operator<(nod b)const{return w>b.w;}};
itn st[oo][oo];
itn x,y,a;
int m,n;
itn f[oo][oo];
priority_queue<nod>q;
void bfs(){
memset(f,0x3f,sizeof(f));
f[1][1] = 0;
q.push((nod){1,1,st[1][1],f[1][1]});
nod top,nxt;
while (!q.empty()){
top = q.top();
q.pop();
if (f[top.x][top.y]<top.w)
continue;
for (itn i=0;i<12;i++){
nxt.x = top.x+dx[i];
nxt.y = top.y+dy[i];
nxt.w = top.w+dw[i];
if (nxt.x<=0||nxt.x>m||nxt.y<=0||nxt.y>m)
continue;
nxt.c = st[nxt.x][nxt.y];
if (!nxt.c)
continue;
if (top.c!=nxt.c)
nxt.w ++;
if (f[nxt.x][nxt.y]>nxt.w){
f[nxt.x][nxt.y]=nxt.w;
q.push(nxt);
}
}
}
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin >> m >> n;
for (itn i=1;i<=n;i++){
cin >> x >> y >> a;
st[x][y] = a+1;
}
bfs();
if (!st[m][m]){
int ans = min(f[m][m-1],f[m-1][m])+2;
if (ans>=inf)
puts("-1");
else cout << ans ;
}
else{
if (f[m][m]==inf)
puts("-1");
else cout << f[m][m];
}
return 0;
}
标签:itn,oo,12,2024.4,nxt,int,return,out
From: https://www.cnblogs.com/white-ice/p/18132165