头像

从TLE开始的WA题之旅




离线:15小时前


最近来访(32)
用户头像
AcWing2AK
用户头像
Crushhh
用户头像
思樊
用户头像
wudima6
用户头像
yxlxszx
用户头像
田所浩二仙贝
用户头像
Aigrl
用户头像
kunmy
用户头像
凌乱之风
用户头像
Wraith_G
用户头像
Finacy
用户头像
繁星.
用户头像
Kaitou
用户头像
辰_5

活动打卡代码 AcWing 3818. 餐厅

#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
int n;const int maxn=5e5+10;
struct node{
    int l,r;
}e[maxn];
bool cmp(node a,node b){
    if(a.r!=b.r) return a.r<b.r;
    return a.l<b.l;
}
int main(){
    cin>>n;
    for(int i=1;i<=n;++i) cin>>e[i].l>>e[i].r;
    sort(e+1,e+1+n,cmp);
    int tot=0;
    int last=e[1].r;tot=1;
    for(int i=2;i<=n;++i)
        if(e[i].l>last) last=e[i].r,++tot;
    cout<<tot<<endl;
    return 0;
}


活动打卡代码 AcWing 3817. 数组

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int na,nb;
    int k,m;
    scanf("%d%d",&na,&nb);
    scanf("%d%d",&k,&m);
    int a[na],b[nb];
    for(int i=0;i<na;i++){
      scanf("%d",&a[i]);
    }
    for (int i = 0; i < nb; i ++ )scanf("%d",&b[i]);
    if(a[k-1]<b[nb-m])printf("YES\n");
    else printf("NO\n");
}


活动打卡代码 AcWing 892. 台阶-Nim游戏

#include<iostream>
#include<algorithm>
using namespace std;
int main(){
    int n;
    scanf("%d",&n);
    int res=0;
    for(int i=1;i<=n;i++){
        int k;
        scanf("%d",&k);
        if(i%2==1){
            res^=k;
        }
    }
    if(res) puts("Yes");
    else puts("No");
    return 0;
}


活动打卡代码 AcWing 890. 能被整除的数

#include<bits/stdc++.h>
using namespace std;
#define re register
#define Re register
#define ll long long
#define MAXN 30
int n,m;
ll ans,p[MAXN];
void dfs(int step,ll cnt,int opt){
    if(cnt > n)return;
    if(step)ans += n / cnt * opt;
    opt = -opt;
    for(Re int i = step + 1;i <= m;i++){
        dfs(i,cnt * p[i],opt);
    }
    return;
}
int main() {
    cin >> n >> m;
    for(Re int i = 1;i <= m;i++){
        cin >> p[i];
    }
    dfs(0,1,-1);
    cout << ans << endl;
    return 0;
}


活动打卡代码 AcWing 3816. 移动元素

#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_set>

using namespace std;

typedef long long LL;

const int N = 100010;

int n;
int a[N], b[N];
LL s[N];

bool check(int w[])
{
    for (int i = 1; i <= n; i ++ )
        s[i] = s[i - 1] + w[i];

    if (s[n] % 2) return false;

    unordered_set<int> S;
    S.insert(0);
    for (int i = 1; i <= n; i ++ )
    {
        S.insert(w[i]);
        if (S.count(s[i] - s[n] / 2)) return true;
    }

    return false;
}

int main()
{
    int T;
    scanf("%d", &T);
    while (T -- )
    {
        scanf("%d", &n);
        for (int i = 1, j = n; i <= n; i ++, j -- )
        {
            scanf("%d", &a[i]);
            b[j] = a[i];
        }
        if (check(a) || check(b)) puts("YES");
        else puts("NO");
    }

    return 0;
}



#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

const int N = 200010, mod = 1e9 + 7;

int n;
int fact[N], infact[N];

int ksm(int a, int k) {
    int res = 1;
    while (k) {
        if (k & 1) res = (LL)res * a % mod;
        a = (LL)a * a % mod;
        k >>= 1;
    }
    return res;
}

void init() {
    fact[0] = infact[0] = 1;
    for (int i = 1; i < N; i++) {
        fact[i] = (LL)fact[i - 1] * i % mod;
        infact[i] = (LL)infact[i - 1] * ksm(i, mod - 2) % mod;
    }
}

int main() {
    init();
    cin >> n;
    int res = (LL)fact[2 * n] * infact[n] % mod * infact[n] % mod * ksm(n + 1, mod - 2) % mod;
    cout << res << endl;
    return 0;
}


活动打卡代码 AcWing 888. 求组合数 IV

#include <bits/stdc++.h>
using namespace std;
const int N=5010;
int primes[N],cnt;
int sum[N];
bool st[N];
void get_primes(int n)
{
    for(int i=2;i<=n;i++)
    {
        if(!st[i])primes[cnt++]=i;
        for(int j=0;primes[j]*i<=n;j++)
        {st[primes[j]*i]=true;if(i%primes[j]==0)break;//==0每次漏
        }}}
// 对p的各个<=a的次数算整除下取整倍数
int get(int n,int p)
{int res =0;while(n){res+=n/p;n/=p;}return res;}
//高精度乘
vector<int> mul(vector<int> a, int b)
{
    vector<int> c;
    int t = 0;
    for (int i = 0; i<a.size(); i ++ ){t += a[i] * b;c.push_back(t % 10);t /= 10; }
    while (t){c.push_back(t % 10);t /= 10;}
    // while(C.size()>1 && C.back()==0) C.pop_back();//考虑b==0时才有pop多余的0 b!=0不需要这行
    return c;
}
int main()
{
    int a,b;
    cin >> a >> b;
    get_primes(a);
    for(int i=0;i<cnt;i++)
    {int p = primes[i];sum[i] = get(a,p)-get(a-b,p)-get(b,p);//是a-b不是b-a
    }
    vector<int> res;
    res.push_back(1);
    for (int i = 0; i < cnt; i ++ )
        for (int j = 0; j < sum[i]; j ++ )//primes[i]的次数
            res = mul(res, primes[i]);

    for (int i = res.size() - 1; i >= 0; i -- ) printf("%d", res[i]);
    puts("");
    return 0;
}


活动打卡代码 AcWing 887. 求组合数 III

#include<iostream>
#include<algorithm>

using namespace std;

typedef long long LL;

int qmi(int a,int k,int p)
{
    int res = 1;
    while(k)
    {
        if(k&1)res = (LL)res*a%p;
        a = (LL)a*a%p;
        k>>=1;
    }
    return res;
}

int C(int a,int b,int p)
{
    if(b>a)return 0;
    int res = 1;
    // a!/(b!(a-b)!) = (a-b+1)*...*a / b! 分子有b项
    for(int i=1,j=a;i<=b;i++,j--)
    {
        res = (LL)res*j%p;
        res = (LL)res*qmi(i,p-2,p)%p;
    }
    return res;
}
//对公式敲
int lucas(LL a,LL b,int p)
{
    if(a<p && b<p)return C(a,b,p);
    return (LL)C(a%p,b%p,p)*lucas(a/p,b/p,p)%p;
}

int main()
{
    int n;
    cin >> n;
    while(n--)
    {
        LL a,b;
        int p;
        cin >> a >> b >> p;
        cout << lucas(a,b,p) << endl;
    }
    return 0;
}



#include <iostream>
#include <algorithm>

using namespace std;

const int N = 110;

int n;
int a[N][N];
int gauss()
{
    int c,r;
    for(c=0,r=0;c<n;c++)
    {
        int t=-1;
        for(int i=r;i<n;i++)
            if(a[i][c])
            {
                t=i;
                break;
            }
        if(t==-1) continue;
        for(int j=c;j<=n;j++) swap(a[r][j],a[t][j]);
        for(int i=r+1;i<n;i++)
            if(a[i][c])
                for(int j=n;j>=c;j--)
                    a[i][j] ^= a[r][j];
        r++;
    }
    if(r<n)
    {
        for(int i=r;i<n;i++)
            if(a[i][n])
                return 2;
        return 1;
    }
    for(int i=n-1;i>=0;i--)    for(int j=i+1;j<n;j++)
            if(a[i][j])a[i][n]^=a[j][n];
    return 0;
}

int main()
{
    cin >> n;
    for(int i=0;i<n;i++)
        for(int j=0;j<=n;j++)
            cin >> a[i][j];
    int t = gauss();
    if(t==0)
    {
        for(int i=0;i<n;i++) cout << a[i][n] << endl;
    }
    else if(t==1) puts("Multiple sets of solutions");
    else puts("No solution");
    return 0;
}



#include <iostream>
#include <algorithm>
#include <cmath>

using namespace std;

const int N = 110;
const double eps = 1e-6;

int n;
double a[N][N];


int gauss()
{
    int c, r         ;                                                     // c 代表 列 col , r 代表 行 row
    for (c = 0, r = 0; c < n; c ++ )                                      //
    {                                                                    //
        int t = r;                                                      // 先找到当前这一列,绝对值最大的一个数字所在的行号
        for (int i = r; i < n; i ++ )                                  //
            if (fabs(a[i][c]) > fabs(a[t][c]))                        //
                t = i;                                               //
                                                                    //
        if (fabs(a[t][c]) < eps) continue;                         // 如果当前这一列的最大数都是 0 ,那么所有数都是 0,就没必要去算了,因为它的约束方程,可能在上面几行
        for (int i = c; i < n + 1; i ++ ) swap(a[t][i], a[r][i]); // 把当前这一行,换到最上面(不是第一行,是第 r 行)去
        for (int i = n; i >= c; i -- ) a[r][i] /= a[r][c];       // 把当前这一行的第一个数,变成 1, 方程两边同时除以 第一个数,必须要到着算,不然第一个数直接变1,系数就被篡改,后面的数字没法算
        for (int i = r + 1; i < n; i ++ )                       // 把当前列下面的所有数,全部消成 0
            if (fabs(a[i][c]) > eps)                           // 如果非0 再操作,已经是 0就没必要操作了
                for (int j = n; j >= c; j -- )                // 从后往前,当前行的每个数字,都减去对应列 * 行首非0的数字,这样就能保证第一个数字是 a[i][0] -= 1*a[i][0];
                    a[i][j] -= a[r][j] * a[i][c];            //
        r ++ ;                                              // 这一行的工作做完,换下一行
    }                                                      //
    if (r < n)                                            // 说明剩下方程的个数是小于 n 的,说明不是唯一解,判断是无解还是无穷多解
    {                                                    // 因为已经是阶梯型,所以 r ~ n-1 的值应该都为 0
        for (int i = r; i < n; i ++ )                   // 
            if (fabs(a[i][n]) > eps)                   // a[i][n] 代表 b_i ,即 左边=0,右边=b_i,0 != b_i, 所以无解。
                return 2;                             //
        return 1;                                    // 否则, 0 = 0,就是r ~ n-1的方程都是多余方程
    }                                               //
                                                   // 唯一解 ↓,从下往上回代,得到方程的解
    for (int i = n - 1; i >= 0; i -- )            //
        for (int j = i + 1; j < n; j ++ )        //
            a[i][n] -= a[j][n] * a[i][j];       //因为只要得到解,所以只用对 b_i 进行操作,中间的值,可以不用操作,因为不用输出

    return 0;
}
int main()
{
    cin >> n;
    for (int i = 0; i < n; i ++ )
        for (int j = 0; j < n + 1; j ++ )
            cin >> a[i][j];
    int t = gauss();
    if (t == 0)
    {
        for (int i = 0; i < n; i ++ ) printf("%.2lf\n", a[i][n]);
    }
    else if (t == 1) puts("Infinite group solutions");
    else puts("No solution");
    return 0;
}