Day7：搜索（一）

T1：PCR

题目链接：PCR
题解：一道结论题，还很好推$$Ans=2^n?2?n$$

代码：

#include<bits/stdc++.h>
#define LL long long
using namespace std;
inline LL read()
{
    LL s=0,w=1;char ch=getchar();while(ch<'0'||ch>'9'){
    if(ch=='-')w=-1;ch=getchar();}while(ch<='9'&&ch>='0')s=s*10+ch-'0',ch=getchar();return s*w;
}
const int mod=19260817;
LL n,ans; 
LL ksm(LL a,LL b)
{
    LL s=1;while(b){
    if(1&b) s=s*a%mod;b>>=1; a=a*a%mod;	}return s%mod;
}
int main()
{
    
// freopen("pcr.in","r",stdin);
// freopen("pcr.out","w",stdout);n=read();ans=(ksm(2,n)-n*2%mod+mod)%mod;printf("%lld",ans);return 0;
}

T2：排列

题目链接：排列
题解：
好不容易想到了要枚举所有$10！$种的方案进行判断就好，可是呢，一个dfs，我还调炸了，，，，，o(╥﹏╥)o
但是很有趣的是，通过这道题，我知道了有一个STL的函数——next_permutation****下一个全排列，还是太菜了，不知道有这样的函数，，，，

代码：

#include<bits/stdc++.h>
#define LL long long
using namespace std;
inline int read()
{
    int s=0,w=1; char ch=getchar();while(ch<'0'||ch>'9'){
    if(ch=='-')w=-1;ch=getchar();}while(ch<='9'&&ch>='0')s=s*10+ch-'0',ch=getchar();return s*w;
}
const int sea=20;
LL ans,x,tot;
int a[sea];
char s[sea];
bool check()
{
    LL s=0;for(int i=1;i<=tot;i++) s=s*10+a[i];if(s%x==0) return 1; else return 0;
}
char ch;
int main()
{
    int T=read();while(T--){
    ans=0;scanf("%s",s+1); tot=strlen(s+1); x=read();for(int i=1;i<=tot;i++) a[i]=s[i]-'0';sort(a+1,a+1+tot);do{
    if(check()) ans++;}while(next_permutation(a+1,a+tot+1));printf("%lld\n",ans);}return 0;
}

T3：新数独

一道毒瘤搜索题，，，，
（然而我还是硬着头皮写完了(╯﹏╰)b，，，，）
这个题，直接看代码吧。

代码：

#include<bits/stdc++.h>
using namespace std;
const int sea=10;
const int pool=4;
int dx[pool]={
    1,-1,0,0};
int dy[pool]={
    0,0,1,-1};
int a[sea][sea][pool],q[sea][sea];
char s[sea][sea];
bool v1[sea][sea],v2[sea][sea],v3[sea][sea];//行，列，宫 
void OK()
{
    for(int i=1;i<=9;i++) {
    for(int j=1;j<=9;j++)printf("%d ",q[i][j]);puts(" ");}
}
bool judge(int x,int y,int z)
{
    for(int i=0;i<4;i++)if(x+dx[i]>=1&&x+dx[i]<=9&&y+dy[i]>=1&&y+dy[i]<=9&&q[x+dx[i]][y+dy[i]]!=-1){
    if(!a[x][y][i]&&z==q[x+dx[i]][y+dy[i]]) return 0;if(a[x][y][i]&&(z-q[x+dx[i]][y+dy[i]])*a[x][y][i]<=0) return 0;} //判断是否符合题目中的大小规则 return 1;
}
bool dfs(int w)
{
    if(w==81) {
    OK(); return 1;}int x=w/9+1,y=w%9+1,z=(x-1)/3*3+(y-1)/3+1;for(int i=1;i<=9;i++)if(!v1[x][i] && !v2[y][i] && !v3[z][i] && judge(x,y,i))//数独常规操作，行，列，宫{
    q[x][y]=i,v1[x][i]=v2[y][i]=v3[z][i]=1;if(dfs(w+1)) return 1;q[x][y]=-1,v1[x][i]=v2[y][i]=v3[z][i]=0;}return 0;
}
int main()
{
    memset(a,0,sizeof(a));memset(v1,0,sizeof(v1));memset(v2,0,sizeof(v2));memset(v3,0,sizeof(v3));for(int i=1;i<=9;i++) for(int j=1;j<=9;j++) q[i][j]=-1;char ch;for(int i=1;i<=9;i++){
     for(int j=1;j<=9;j++)if(j%3){
    ch=getchar();while(ch!='<'&&ch!='>') ch=getchar();if(ch=='<') a[i][j][2]=-1,a[i][j+1][3]=1;else a[i][j+1][3]=-1,a[i][j][2]=1;}if(i%3){
    for(int j=1;j<=9;j++){
    ch=getchar();while(ch!='^'&&ch!='v') ch=getchar();if(ch=='^') a[i][j][0]=-1,a[i+1][j][1]=1;else a[i+1][j][1]=-1,a[i][j][0]=1;}}}if(!dfs(0)) printf("CTRSB\n"); return 0;
}

耐得住寂寞，享得住繁华。——Blng