头像

KaMtuo

春日部防卫队




在线 


活动打卡代码 AcWing 1208. 翻硬币

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;
}


活动打卡代码 AcWing 95. 费解的开关

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;
vector<int>add;
int one;

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

        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;
             add.push_back(i);
            ones(u + 1);
            add.pop_back();
            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;
}


活动打卡代码 AcWing 754. 平方矩阵 II

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;
}


活动打卡代码 AcWing 717. 简单斐波那契

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]);
    }
}


活动打卡代码 AcWing 1209. 带分数

KaMtuo
19小时前

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

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

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

        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;
             add.push_back(i);
            ones(u + 1);
            add.pop_back();
            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];
int add[20];
void dfs(int u){
    if(u>n){
        for(int i=1;i<=n;i++){printf("%d ",add[i]);

        }
        puts("");
        return;
    }
    for(int i=1;i<=n;i++){
        if(!st[i])
        {
            st[i]=true;
            add[u]=i;
            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;
}