当前位置：首页 > news >正文

2022/8/30

news 来源：原创 2024/5/20 13:04:51

735D - Taxes 哥德巴赫猜想

哥德巴赫猜想：任何大于等于4的偶数可以表示成两个素数的和。

然后这题就做完了，，，

是偶数除了2答案是1外别的都是2，奇数的话先看是不是素数，不是的话就看看n-2是不是素数，再不行那答案就是3了，3,n-3，因为n-3是偶数所以答案是3

(1条消息) D. Taxes（哥德巴赫猜想）_·马克图布·的博客-CSDN博客

#include <bits/stdc++.h>
#define ll long long
#define lowbit(i) (i)&(-i)
using namespace std;
const int mod=1e9+7;
const ll inf=1e18;
const double eps=1e-8;
int qpow(ll a,ll b){
    ll res=1;
    while(b){
        if(b&1) res=res*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return res;
}
ll getinv(ll a){return qpow(a,mod-2);}
ll lcm(ll a,ll b){
    return a*b/__gcd(a,b);
}
bool cmp(ll a,ll b){return a>b;}
//ll C(ll a,ll b){
//    return (fac[a]*getinv(fac[a-b])%mod)*getinv(fac[b])%mod;
//}
ll n;
bool su(ll x){
    for(int i=2;i<=sqrt(x);i++)
        if(x%i==0) return 0;
    return 1;
}
int main(){
    scanf("%lld",&n);
    if(n==2) printf("1\n");
    else{
        if(n&1){
            if(su(n)) printf("1\n");
            else if(su(n-2)) printf("2\n");
            else printf("3\n");
        }
        else printf("2\n");
    }
    return 0;
}

1303C - Perfect Keyboard

可以发现一般情况下只有当有两个字母只和1个相邻也就是入度为1，其他的字母都是和2个相邻也就是入度为2时才会有解，然后就是先从度数为1的开始，然后一直遍历到度数为1的结束，然后在把剩下的字母给输出就可以，模拟这个思路就像，特判就是|s|==1的时候

#include <bits/stdc++.h>
#define ll long long
#define lowbit(i) (i)&(-i)
using namespace std;
const int mod=1e9+7;
const ll inf=1e18;
const double eps=1e-8;
int qpow(ll a,ll b){
    ll res=1;
    while(b){
        if(b&1) res=res*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return res;
}
ll getinv(ll a){return qpow(a,mod-2);}
ll lcm(ll a,ll b){
    return a*b/__gcd(a,b);
}
bool cmp(ll a,ll b){return a>b;}
//ll C(ll a,ll b){
//    return (fac[a]*getinv(fac[a-b])%mod)*getinv(fac[b])%mod;
//}
ll t,in[30];
char s[205];
vector<char>v[30];
bool vis[30][30];
map<char,bool>mp;
int main(){
    scanf("%lld",&t);
    while(t--){
        scanf("%s",s+1);
        ll n=strlen(s+1);
        if(n==1){
            cout<<"YES\n"<<s[1];
            for(char i='a';i<='z';i++)
                if(i!=s[1]) cout<<i;
            printf("\n");
            continue;
        }
        mp.clear();
        for(int i=1;i<=26;i++) in[i]=0,v[i].clear();
        for(int i=1;i<=26;i++)
            for(int j=1;j<=26;j++) vis[i][j]=0;
        for(int i=2;i<=n;i++){
            if(!vis[s[i]-'a'+1][s[i-1]-'a'+1]){
                vis[s[i]-'a'+1][s[i-1]-'a'+1]=vis[s[i-1]-'a'+1][s[i]-'a'+1]=1;
                v[s[i]-'a'+1].push_back(s[i-1]);
                v[s[i-1]-'a'+1].push_back(s[i]);
                in[s[i]-'a'+1]++;
                in[s[i-1]-'a'+1]++;
            }
        }
        ll flag=0,ma=0;
        for(int i=1;i<=26;i++){
            if(in[i]==1) flag++,ma=i;
            else if(in[i]>2){
                flag=0;break;
            }
        }
        if(flag!=2){printf("NO\n");continue;}
        printf("YES\n");
        while(1){
            ll fg=0;
            cout<<(char)(ma-1+'a');
            mp[(char)(ma-1+'a')]=1;
            for(int i=0;i<v[ma].size();i++){
                char j=v[ma][i];
                if(mp[j]) continue;
                ma=j-'a'+1;
                fg=1;
                break;
            }
            if(!fg) break;
        }
        for(char i='a';i<='z';i++)
        if(!mp[i]){cout<<i;mp[i]=1;}
        printf("\n");
    }
    return 0;
}

P3389 【模板】高斯消元法 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) 高斯约旦消元法模板

还以为是什么高大上的算法，原来是当时矩阵化简乘最简矩阵的实现而已，，

洛谷P3389 【模板】高斯消元高斯-约旦消元法_Skydogli的博客-CSDN博客

#include <bits/stdc++.h>
#define ll long long
#define lowbit(i) (i)&(-i)
using namespace std;
const int mod=1e9+7;
const ll inf=1e18;
const double eps=1e-8;
int qpow(ll a,ll b){
    ll res=1;
    while(b){
        if(b&1) res=res*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return res;
}
ll getinv(ll a){return qpow(a,mod-2);}
ll lcm(ll a,ll b){
    return a*b/__gcd(a,b);
}
bool cmp(ll a,ll b){return a>b;}
//ll C(ll a,ll b){
//    return (fac[a]*getinv(fac[a-b])%mod)*getinv(fac[b])%mod;
//}
ll n;
double a[110][110];
int main(){
    scanf("%lld",&n);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n+1;j++)
        scanf("%lf",&a[i][j]);
    for(int i=1;i<=n;i++){
        int p=i;
        for(int j=i+1;j<=n;j++)
            if(fabs(a[j][i])>fabs(a[p][i])) p=j;
        swap(a[i],a[p]);
        if(fabs(a[i][i])<1e-15){
            printf("No Solution");
            return 0;
        }
        for(int j=1;j<=n;j++)
        if(j!=i){
            double tmp=a[j][i]/a[i][i];
            for(int k=i+1;k<=n+1;k++)
                a[j][k]-=a[i][k]*tmp;
        }
    }
    for(int i=1;i<=n;i++)
        printf("%.2lf\n",a[i][n+1]/a[i][i]);
    return 0;
}

P2455 [SDOI2006]线性方程组 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) 高斯消元

这题多了个无穷解的判断，需要对模板做一些调整，如果这一列都是0的话，那么应该去下一列再去进行原来的操作，如果遍历完之后发现用的行数少于n那么就一定是特殊情况，因为只要有一个主元是0就是无解，所以先判无解，然后如果b都是0的话那就是无穷解

题解 P2455 【[SDOI2006]线性方程组】 - Piwry - 洛谷博客

#include <bits/stdc++.h>
#define ll long long
#define lowbit(i) (i)&(-i)
using namespace std;
const int mod=1e9+7;
const ll inf=1e18;
const double eps=1e-8;
int qpow(ll a,ll b){
    ll res=1;
    while(b){
        if(b&1) res=res*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return res;
}
ll getinv(ll a){return qpow(a,mod-2);}
ll lcm(ll a,ll b){
    return a*b/__gcd(a,b);
}
bool cmp(ll a,ll b){return a>b;}
//ll C(ll a,ll b){
//    return (fac[a]*getinv(fac[a-b])%mod)*getinv(fac[b])%mod;
//}
ll n;
double a[110][110];
int main(){
    scanf("%lld",&n);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n+1;j++)
        scanf("%lf",&a[i][j]);
    ll nwline=1;
    for(int k=1;k<=n;k++){
        ll p=nwline;
        for(int i=nwline+1;i<=n;i++)
            if(fabs(a[p][k])<fabs(a[i][k])) p=i;
        if(a[p][k]==0) continue;
        swap(a[nwline],a[p]);
        for(int i=1;i<=n;i++){
            if(i==nwline) continue;
            double tmp=a[i][k]/a[nwline][k];
            for(int j=k+1;j<=n+1;j++)
                a[i][j]-=a[nwline][j]*tmp;
        }
        nwline++;
    }
    if(nwline<=n){
        while(nwline<=n)
        if(a[nwline++][n+1]!=0){printf("-1\n");return 0;}
        printf("0\n");return 0;
    }
    for(int i=1;i<=n;i++)
        printf("x%lld=%.2lf\n",i,a[i][n+1]/a[i][i]);
    return 0;
}

P4783 【模板】矩阵求逆 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

就是用的线代中最基础的方法求得逆矩阵，只是在高斯消元的基础上改一下就可以了

矩阵求逆 —— 初等变换法（高斯-约旦消元） - 一只萌新~ - 洛谷博客

#include <bits/stdc++.h>
#define ll long long
#define lowbit(i) (i)&(-i)
using namespace std;
const int mod=1e9+7;
const ll inf=1e18;
const double eps=1e-8;
int qpow(ll a,ll b){
    ll res=1;
    while(b){
        if(b&1) res=res*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return res;
}
ll getinv(ll a){return qpow(a,mod-2);}
ll lcm(ll a,ll b){
    return a*b/__gcd(a,b);
}
bool cmp(ll a,ll b){return a>b;}
//ll C(ll a,ll b){
//    return (fac[a]*getinv(fac[a-b])%mod)*getinv(fac[b])%mod;
//}
ll n,a[1005][1005];
int main(){
    scanf("%lld",&n);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++) scanf("%lld",&a[i][j]);
        a[i][i+n]=1;
    }
    for(int i=1;i<=n;i++){
        ll p=i;
        for(int k=i+1;k<=n;k++)
            if(a[k][i]>a[p][i]) p=k;
        if(a[p][i]==0){
            printf("No Solution");return 0;
        }
        swap(a[p],a[i]);
        ll tmp=getinv(a[i][i]);
        for(int j=1;j<=n;j++){
            if(j==i) continue;
            ll mul=a[j][i]*tmp%mod;
            for(int k=i;k<=(n<<1);k++){
                a[j][k]=((a[j][k]-a[i][k]*mul%mod)%mod+mod)%mod;
            }
        }
        for(int j=1;j<=(n<<1);j++) a[i][j]=a[i][j]*tmp%mod;
    }
    for(int i=1;i<=n;i++){
        for(int j=n+1;j<=(n<<1);j++) printf("%lld ",a[i][j]);
        printf("\n");
    }
    return 0;
}