题意：给n，使满足式子a+b/c=n，其中a，b，c共同恰好由1，2...9组成，求a，b，c的取值种数
思路1：枚举出9个数的全排列（可使用next_permutation() ），再用两重循环暴力分解出三段，每段分别代表a，b，c，若满足式子则计数
注意：判断b/c是否为整除
1 int main(){
2 int n,a[10]={0,1,2,3,4,5,6,7,8,9},ans;
3 cin>>n;
4 while(1){
5 int x=0;
6 for(int i=1;i<=7;++i){
7 x=x*10+a[i];
8 int y=0;
9 for(int j=i+1;j<=8;++j){
10 y=y*10+a[j];
11 int k=0;
12 for(int u=j+1;u<=9;++u){
13 k=k*10+a[u];
14 }
15 if(y%k==0&&x+y/k==n){
16 ans++;
17 }
18 }
19 }
20 next_permutation(a+1,a+10);
21
22 //判断全排列是否重复
23
24 int ok=0;
25 for(int i=1;i<=9;++i){
26 if(a[i]!=i){
27 ok=1;
28 break;
29 }
30 }
31 if(!ok)break;
32 }
33 cout<<ans;
34 return 0;
35 }
思路2：式子转换为 n * c =a * c +b ，先枚举a，对于每个a再枚举c，则可通过式子求b，再判断b是否符合
const int N=520;
int had_use[N],cp[N];
int ans=0;
int n;
bool check(int a,int c)
{
int b = n * c - a * c;
if(!a||!b||!c)return false;
memcpy(cp,had_use,sizeof had_use);//防改变已用数字
while(b)
{
int t=b%10;
b/=10;
if(!t||cp[t])return false;//b是否含0以及与已用数字重复
cp[t]=1;
}
for(int i=1;i<=9;i++)//是否用完9个数
if(!cp[i])
return false;
return true;
}
void dfs_c(int x,int a,int c)
{
if(x>9)return;
if(check(a,c))ans++;
for(int i=1;i<=9;i++)
if(!had_use[i])
{
had_use[i]=1;
dfs_c(x+1,a,c*10+i);//枚举c的下一层
had_use[i]=0;//用完还原
}
}
void dfs_a(int x,int a)
{
if(a>=n)return;
if(a)dfs_c(x,a,0);//枚举c,分别表示：已用数目，a的值，c的值
for(int i=1;i<=9;i++)//枚举当前位置的可用数字
if(!had_use[i])
{
had_use[i]=1;
dfs_a(x+1,a*10+i); //枚举a的下一层
had_use[i]=0;//用完还原
}
}
int main()
{
cin>>n;
dfs_a(0,0);//分别表示：已经用了多少个数字 , 当前的a的值
cout<<ans;
return 0;
}
题意：在若干连续的数中，找出一个缺少的数和一个重复的数
思路：将所有数排序后枚举一边
注意：读入若干数据可用 while(cin>>x) 或 while(scanf("%d",&x)!=EOF)
1 int main(){
2 int n,x,a[100005],e,f;
3 cin>>n;
4 while(cin>>x)a[x]++;
5 for(int i=1;;++i){
6 if(a[i-1]&&a[i+1]&&!a[i])e=i;
7 if(a[i]>1)f=i;
8 if(e&&f)break;
9 }
10 cout<<e<<' '<<f;
11 return 0;
12 }
题意：给出两个由两个字符组成的等长字符串，求a串变b串的最小操作数，每次操作翻转相邻的两个字符
思路：由题可知，出现不同的次数一定为偶数，保证操作数最小，找出依次出现的两个不同位置即可
1 int main(){
2 char a[1005],b[1005];
3 int c[1005]={0},k=1,s=0;
4 cin>>a+1>>b+1;
5 for(int i=1;a[i];++i){
6 if(a[i]!=b[i])c[k++]=i;
7 }
8 for(int i=1;c[i];++i)
9 {
10 if(i%2)s-=c[i];
11 else s+=c[i];
12 }
13 cout<<s;
14 return 0;
15 }
题意：a1~an中对[2,n-1]中任意的数进行( ai−1 ，ai ，ai+1 )←( ai−1 + ai ，−ai ，ai+1 + ai )，使amax最小
思路：每对 ai 进行一次操作等同于将前缀和 si 与 si-1 进行交换，要使得amax最小，即前缀和之差的最大值最小，需使 s[ ] 尽可能单调排列，且需考虑s[n]固定，可以外加s[0]也固定，将问题转化为一个数组内除首位以外都可任意排序，通过画图可知有两个拐点的曲线重叠部分最小时，单调部分最多，该曲线满足：1.左端点小于右端点 2.极小值在极大值左边
1 typedef long long LL;
2 const int N = 3e5 + 10;
3 int t, n;
4 LL s[N], a[N];
5 bool v[N];
6 int main()
7 {
8 cin >> t;
9 while (t--)
10 {
11 cin >> n;
12 memset(v, 0, sizeof v);
13 for (int i = 1; i <= n; i++)
14 cin >> s[i], s[i] += s[i - 1];
15
16 LL s0 = s[0], sn = s[n];
17 if (s0 > sn)
18 swap(s0, sn);
19 sort(s, s + n + 1);
20
21 for (int i = 0; i <= n; i++)
22 if (s[i] == s0)
23 {
24 s0 = i;
25 break;
26 }
27 for (int i = n; i >= 0; i--)
28 if (s[i] == sn)
29 {
30 sn = i;
31 break;
32 }
33 int l = 0, r = n;
34 for (int i = s0; i >= 0; i -= 2)
35 {
36 a[l++] = s[i];
37 v[i] = 1;
38 }
39 for (int i = sn; i <= n; i += 2)
40 {
41 a[r--] = s[i];
42 v[i] = 1;
43 }
44 for (int i = 0; i <= n; i++)
45 if (!v[i])
46 a[l++] = s[i];
47 LL res = 0;
48 for (int i = 1; i <= n; i++)
49 res = max(res, abs(a[i] - a[i - 1]));
50 cout << res << endl;
51 }
52 return 0;
53 }
题意：用 n个＋ 和 m个 - 和 n+m+1 个数 构成一个值最大的后缀表达式
思路：最大值为 max + ( {...} ) - （ min {...} )；若没有‘-’，最大值即为全部数的和；若有‘-’，只需减去最小的数和加上最大的数，再加上剩余数的绝对值即可；
int main(){
int n,m,a[200010],tmp[200010];
cin>>n>>m;
for(int i=0;i<m+n+1;++i)
cin>>a[i];
long long s=0;
if(!m){
for(int i=0;i<m+n+1;++i)
s+=a[i];
cout<<s;
}
else{
sort(a,a+m+n+1);
for(int i=0;i<m+n+1;++i){
if(i==0)s-=a[i];
else if(i==m+n)s+=a[i];
else
s+=abs(a[i]);
}
cout<<s;
}
return 0;
}
题意：给出n个数，求包含这n个数的等差数列的最小长度
思路：公差越大，长度越小；排列后，由于每个数与第一个数的差都为公差的倍数，枚举求出最大公差，由公式（An - A1）/公差 +1 求出最小长度，当公差为0时最小长度即为n
int gcd(int a,int b){
if(b==0)return a;
return gcd(b,a%b);
}
int main(){
int n,a[100005],d;
cin>>n;
for(int i=0;i<n;++i)
cin>>a[i];
sort(a,a+n);
for(int i=0;i<n;++i){
if(i==1)d=a[i]-a[0];
else if(i>1) d=gcd(d,a[i]-a[0]);
}
if(!d)cout<<n;
else cout<<(a[n-1]-a[0])/d+1;
return 0;
}
题意：求1~n中所有包含2，0，1，9（不含前缀0）的数的和
思路：一一枚举
1 bool check(int x){
2 if(x==2||x==0||x==1||x==9)
3 return true;
4 return false;
5 }
6 int main(){
7 cin.tie(0),cout.tie(0);
8 int n,s=0;
9 cin>>n;
10 for(int i=1;i<=n;++i){
11 if(i<10){
12 if(check(i))s+=i;
13 }
14 else{
15 int y=i,k=1;
16 while(y/10){
17 if(check(y%10)){
18 s+=i;k=0;break;
19 }
20 y/=10;
21 }
22 if(k&&(y==2||y==1||y==9))s+=i;
23 }
24 }
25 cout<<s;
26 return 0;
27 }
题意：给出一颗包含n个节点的完全二叉树，问哪一层的权值之和最大
思路：枚举，2h-1作为分段点求和
1 int main(){
2 long long s,ma=-1e18,n,a[100005];
3 cin>>n;
4 for(int i=1;i<=n;++i)
5 cin>>a[i];
6 int h=1,res=1;
7 for(int i=1;i<=n;i*=2){
8 s=0;
9 for(int j=i;j<=i*2-1&&j<=n;++j)
10 s+=a[j];
11 if(s>ma){
12 ma=s;
13 res=h;
14 }
15 h++;
16 }
17 cout<<res;
18 return 0;
19 }
标签：Winter,1.2,int,cin,蓝桥,ai,main,题意 From： https://www.cnblogs.com/bible-/p/17023123.html