KaMtuo

351

KaMtuo
29分钟前

https://www.acwing.com/problem/content/description/1210/

#include<bits/stdc++.h>
using namespace std;
string a,b;
int main(){
cin>>a>>b;
int ans=0;
for(int i=0;i<a.size()-1;i++)
{
if(a[i]!=b[i]){a[i+1]='o'+'*'-a[i+1];

ans++;
}
}
cout<<ans;
return 0;
}


KaMtuo
1小时前

https://www.acwing.com/problem/content/97/

#include<bits/stdc++.h>
using namespace std;
const int N=10;
int sum;
int zero,ze;
int n;
int light[N][N];
int ans[N][N];
int a[]={0,0,1,-1},b[]={1,-1,0,0};
void show(){
for(int i=1;i<=5;i++){
for(int j=1;j<=5;j++)
{
cout<<light[i][j];
}
puts("");
}
puts("");
}
void change(int i,int j)
{
sum++;
light[i][j]=1-light[i][j];
if(light[i][j]==1)zero--;
else if(!light[i][j])zero++;
for(int k=0;k<4;k++)
{
light[i+a[k]][j+b[k]]=1-light[i+a[k]][j+b[k]];
if(light[i+a[k]][j+b[k]]==1)zero--;
else if(!light[i+a[k]][j+b[k]]) zero++;
}
}
int main(){

cin>>n;
while(n--)
{
ze=0;
memset(ans,-1,sizeof ans);
for(int i=1;i<=5;i++)
for(int j=1;j<=5;j++)
{
scanf("%1d",&ans[i][j]);
if(ans[i][j]==0)ze++;
}
int a=7;
//int kk=0;
//show();
for(int i=0;i<1<<5;i++)
{
memcpy(light,ans,sizeof ans);
//show();
sum=0;
zero=ze;
int p=i;
int j=1;

while(p)
{
if(p%2)change(1,j);
p/=2;
j++;
}

for(int e=1;e<=4;e++)
for(int z=1;z<=5;z++)
if(light[e][z]==0)change(e+1,z);
// cout<<i<<' '<<sum<<' '<<zero<<endl;
if(sum<=6&&zero==0)
a=min(a,sum);

}
if(a>6)cout<<-1<<endl;
else cout<<a<<endl;
}
// cout<<sum;
return 0;
}


KaMtuo
3小时前

https://www.acwing.com/problem/content/description/1211/

### 优化前

4906ms

#include<bits/stdc++.h>
using namespace std;
int n;
bool st[10];
int ans = 0;
int one;

void ones(int u)
{
if (u > 9)
{
/* one = 0;
for (int i = 0; i < add.size(); i++) {
}*/

for (int i = 0; i < 7; i++) {

for (int j = i+2; j < 9; j++)
{
int a = 0, b = 0, c = 0;
for (int k = 0; k <= i; k++)a = a * 10 + add[k];
for (int l = i + 1; l < j; l++)b = b * 10 + add[l];
for (int f = j; f < 9; f++)c = c * 10 + add[f];
// cout << a << b << c << endl;
if (a + b / c == n && b % c == 0)ans++;
}

}

return;

}

for (int i = 1; i < 10; i++) {
if (!st[i]) {
st[i] = true;
ones(u + 1);
st[i] = false;

}

}
}
int main() {
cin >> n;

ones(1);
cout << ans;
return 0;
}


### 优化后

857ms

#include<bits/stdc++.h>
using namespace std;
const int N=20;
int n;
int st[N],st2[N];
int ans;
bool check(int a,int b,int u)
{
int c=(n-a)*b;
int s=c;
int z=0;
// if(a==3&&b==714)printf("12");
// printf("%d\n",b);
memcpy(st2,st,sizeof st);
while(c)
{
st2[c%10]=true;
//    cout<<c%10;
c/=10;
z++;
}
// cout<<z;
for(int i=1;i<=9;i++)
{
if(!st2[i]){return false;}
}
//cout<<a<<b<<endl;//<<s<<endl;
// cout<<z<<u;
//  if(a==3&&b==714)printf("%d %d",z, u);
return (z==9-u);
}
void _b(int u,int a,int b)
{
// if(b)cout<<b<<endl;
if(u==9)return ;

else if(b&&check(a,b,u-1)){ans++;}

for(int i=1;i<=9;i++)
{
if(!st[i])
{
st[i]=true;
_b(u+1,a,b*10+i);
st[i]=false;
}
}
}
void _a(int u,int a)
{
if(u==7||a>=n)return ;
else if(a){_b(u+1,a,0);}
for(int i=1;i<=9;i++)
{
if(!st[i]){
st[i]=true;
_a(u+1,a*10+i);
st[i]=false;
//_a(u+1,a);
}
}
}
int main(){
cin>>n;
_a(0,0);
cout<<ans;
//cout<<check(3,714,4);
return 0;
}


KaMtuo
5小时前

https://www.acwing.com/problem/content/description/756/

#include<bits/stdc++.h>
using namespace std;
const int N=200;
int n;
int ans[N][N];
int main(){
for(int i=1;i<=100;i++)
{
int h=1;
for(int j=i;j>=1;j--)
ans[i][j]=ans[j][i]=h++;
}
while(1){
cin>>n;
if(!n)break;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++)
cout<<ans[i][j]<<' ';
puts("");
}
puts("");
}
return 0;
}


KaMtuo
5小时前
#include<bits/stdc++.h>
using namespace std;
const int N=200;
int n;
int ans[N][N];
int main(){
for(int i=1;i<=100;i++)
{
int h=1;
for(int j=i;j>=1;j--)
ans[i][j]=ans[j][i]=h++;
}
while(1){
cin>>n;
if(!n)break;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++)
cout<<ans[i][j]<<' ';
puts("");
}
puts("");
}
return 0;
}


KaMtuo
18小时前

https://www.acwing.com/problem/content/719/

#include<bits/stdc++.h>
using namespace std;
const int N=100;
int ans[N];
int main(){
ans[1]=0;
ans[2]=ans[3]=1;
int  n;
cin>>n;
for(int i=1;i<=n;i++){
if(i>=3)ans[i]=ans[i-1]+ans[i-2];
printf("%d ",ans[i]);
}
}


KaMtuo
19小时前

https://www.acwing.com/problem/content/1211/

#include<bits/stdc++.h>
using namespace std;
int n;
bool st[10];
int ans = 0;
int one;

void ones(int u)
{
if (u > 9)
{
/* one = 0;
for (int i = 0; i < add.size(); i++) {
}*/

for (int i = 0; i < 7; i++) {

for (int j = i+2; j < 9; j++)
{
int a = 0, b = 0, c = 0;
for (int k = 0; k <= i; k++)a = a * 10 + add[k];
for (int l = i + 1; l < j; l++)b = b * 10 + add[l];
for (int f = j; f < 9; f++)c = c * 10 + add[f];
// cout << a << b << c << endl;
if (a + b / c == n && b % c == 0)ans++;
}

}

return;

}

for (int i = 1; i < 10; i++) {
if (!st[i]) {
st[i] = true;
ones(u + 1);
st[i] = false;

}

}
}
int main() {
cin >> n;

ones(1);
cout << ans;
return 0;
}


KaMtuo
21小时前

https://www.acwing.com/problem/content/95/

#include<bits/stdc++.h>
using namespace std;
const int N = 30;
int n;
int m;
int sum = 0;
vector<int >ans;
bool st[N];

void dfs(int u) {

if (sum == m)

{
for (int i = 1; i <= n; i++)if (st[i])printf("%d ", i);
puts("");
return;
}
else if (u > n)return;
st[u] = true;
sum++;
dfs(1 + u);
//ans.pop_back();
sum--;
st[u] = false;
dfs(u + 1);
}
int main() {
cin >> n >> m;
dfs(1);
return 0;
}



KaMtuo
21小时前

https://www.acwing.com/problem/content/96/

#include<bits/stdc++.h>
using namespace std;
int n;
bool st[20];
void dfs(int u){
if(u>n){

}
puts("");
return;
}
for(int i=1;i<=n;i++){
if(!st[i])
{
st[i]=true;
dfs(u+1);
st[i]=false;
}
}
}
int main(){
cin>>n;
dfs(1);
return 0;
}



KaMtuo
21小时前

https://www.acwing.com/problem/content/94/

#include<bits/stdc++.h>
using namespace std;
const int N=20;
int n;
bool state[N];
void dfs(int u){
if(u>n){
for(int i=1;i<=n;i++){
if(state[i])printf("%d ",i  );
}
puts("");
return ;
}
state[u]=true;
dfs(u+1);
state[u]=false;
dfs(u+1);
}
int main(){
// n;
scanf("%d",&n);
dfs(1);
return 0;
}