多校不会题选讲(四)

完了,太菜了,没办法,真的只会写四题,其他以后加油补吧。。。

T4:Nothing is Impossible

题意:

给定n个题目,每个题目1个正确选项b个错误的,让我们选择一个子集S使得有人可以将这S个题全做对。。。

分析:

2018-08-03 10-58-10屏幕截图

代码:

#include<bits/stdc++.h>
#define LL long long
using namespace std;
const LL N=25;
const LL mod=1e9+7;
const LL inf=0x3f3f3f3f;
namespace FastIO
{
    template inline void read(tp &x)
    {
        x=0; register char c=getchar(); register bool f=0;
        for(;c'9';f|=(c=='-'),c = getchar());
        for(;c>='0'&&c<='9';x=(x<<3)+(x<<1)+c-'0',c = getchar());
        if(f) x=-x;
    }
    template inline void write(tp x)
    {
        if (x==0) return (void) (putchar('0'));
        if (x<0) putchar('-'),x=-x;
        LL pr[20]; register LL cnt=0;
        for (;x;x/=10) pr[++cnt]=x%10;
        while (cnt) putchar(pr[cnt--]+'0');
    }
    template inline void writeln(tp x)
    {
        write(x);
        putchar('\n');
    }
}
using namespace FastIO;
int T, n, m;
struct Node{int a, b;} p[150];
bool cmp(Node a, Node b){return a.b < b.b;}
int main()
{
    read(T);
    while (T--)
    {
        read(n),read(m);
        for (int i = 1; i <= n; i++)
            read(p[i].a),read(p[i].b);
        sort(p + 1, p + n + 1, cmp);
        int ans=0;
        for (int i = 1; i <= n; i++)
        {
            m /= p[i].b + 1;
            if (m) ans++;
            else break;
        }
        writeln(ans);
    }
    return 0;
}

T5:Matrix from Arrays

题意:

给出一种矩阵生成方法,然后问你其中一个子矩阵的sum值。。。

分析:

大力打表找规律,然后前缀和搞一搞。。。

代码:

#include<bits/stdc++.h>
#define LL long long
using namespace std;
const LL N=100;
const LL mod=1e9+7;
const LL inf=0x3f3f3f3f;
namespace FastIO
{
    template inline void read(tp &x)
    {
        x=0; register char c=getchar(); register bool f=0;
        for(;c'9';f|=(c=='-'),c = getchar());
        for(;c>='0'&&c<='9';x=(x<<3)+(x<<1)+c-'0',c = getchar());
        if(f) x=-x;
    }
    template inline void write(tp x)
    {
        if (x==0) return (void) (putchar('0'));
        if (x<0) putchar('-'),x=-x;
        LL pr[20]; register LL cnt=0;
        for (;x;x/=10) pr[++cnt]=x%10;
        while (cnt) putchar(pr[cnt--]+'0');
    }
    template inline void writeln(tp x)
    {
        write(x);
        putchar('\n');
    }
}
using namespace FastIO;
#define F(_) for(int _=0;_<L;++_)
using namespace std;
int a[15],L,sum;
int m[N][N],sumr[N],sumc[N];
long long get(int x,int y)
{
    long long res=0;
    int l=x/L,r=y/L;res+=1ll*l*r*sum;
    if(x%L)res+=1ll*sumr[x%L-1]*r;
    if(y%L)res+=1ll*sumc[y%L-1]*l;
    l=x%L,r=y%L;
    for(int i=0;i<l;++i)
        for(int j=0;j<r;++j)
            res+=m[i][j];
    return res;
}
main()
{
    int T;read(T);
    for(int cas=0;cas<T;++cas)
    {
        read(L);
        F(i)read(a[i]);
        int p=0;
        for(int i=0;i<4*L;++i)
            for(int j=0;j<=i;++j)
                m[j][i-j]=a[p],p=(p+1)%L;
        sum=0;L*=2;
        F(i)sumr[i]=sumc[i]=0;
        F(i)F(j)sum+=m[i][j];
        F(i)
        {
            F(j)sumr[i]+=m[i][j];
            if(i)sumr[i]+=sumr[i-1];
        }
        F(j)
        {
            F(i)sumc[j]+=m[i][j];
            if(j)sumc[j]+=sumc[j-1];
        }
        int q;read(q);
        for(;q--;)
        {
            int x0,y0,x1,y1;
            read(x0),read(y0),read(x1),read(y1);
            writeln(get(x1+1,y1+1)+get(x0,y0)-get(x1+1,y0)-get(x0,y1+1));
        }
    }
    return 0;
}

T11:Expression in Memories

题意:

给你一个字符串,其中有一部分“?”然后让你填充它们,使得式子变成合法表达式。。。

分析:

注意在类似 +0? 的情况下, ? 须被替换为 + 或 * ,其余情况直接将 ? 替换为非零数字就好。替换完成后判断一下是否合法。

代码:

#include<bits/stdc++.h>
#define LL long long
using namespace std;
const LL N=25;
const LL mod=1e9+7;
const LL inf=0x3f3f3f3f;
namespace FastIO
{
    template inline void read(tp &x)
    {
        x=0; register char c=getchar(); register bool f=0;
        for(;c'9';f|=(c=='-'),c = getchar());
        for(;c>='0'&&c<='9';x=(x<<3)+(x<<1)+c-'0',c = getchar());
        if(f) x=-x;
    }
    template inline void write(tp x)
    {
        if (x==0) return (void) (putchar('0'));
        if (x<0) putchar('-'),x=-x;
        LL pr[20]; register LL cnt=0;
        for (;x;x/=10) pr[++cnt]=x%10;
        while (cnt) putchar(pr[cnt--]+'0');
    }
    template inline void writeln(tp x)
    {
        write(x);
        putchar('\n');
    }
}
using namespace FastIO;
int T;
string s;
int main()
{
    cin >> T;
    while (T--)
    {
        cin >> s;
        int flag = 1;
        for (int i = 1; i < s.size(); ++i)
            if (s[i] == '?' && s[i - 1] == '0' && (i == 1 || s[i - 2] == '+' || s[i - 2] == '*'))
                s[i] = '+';
        for (int i = 0; i < s.size(); ++i)
            if (s[i] == '?')
                s[i] = '1';
        if (s[0] == '+' || s[0] == '*')
            flag = 0;
        if (s[s.size() - 1] == '+' || s[s.size() - 1] == '*')
            flag = 0;
        for (int i = 0; i < s.size() - 1; ++i)
            if ((s[i] == '+' || s[i] == '*') && (s[i + 1] == '+' || s[i + 1] == '*'))
                flag = 0;
        for (int i = 0; i < s.size() - 1; ++i)
            if ((i == 0 || s[i - 1] == '+' || s[i - 1] == '*') && (s[i] == '0') && (s[i + 1] != '+' && s[i + 1] != '*'))
                flag = 0;
        if (flag)
            cout << s << endl;
        else
            cout << "IMPOSSIBLE" << endl;
    }
    return 0;
}

T12:Graph Theory Homework

题意:水题自己看。。。

分析:自己搞。。。

代码:

#include<bits/stdc++.h>
#define LL long long
using namespace std;
const LL N=1e5+10;
const LL mod=1e6;
const LL inf=0x3f3f3f3f3f;
namespace FastIO
{
    template inline void read(tp &x)
    {
        x=0; register char c=getchar(); register bool f=0;
        for(;c'9';f|=(c=='-'),c = getchar());
        for(;c>='0'&&c<='9';x=(x<<3)+(x<<1)+c-'0',c = getchar());
        if(f) x=-x;
    }
    template inline void write(tp x)
    {
        if (x==0) return (void) (putchar('0'));
        if (x<0) putchar('-'),x=-x;
        LL pr[20]; register LL cnt=0;
        for (;x;x/=10) pr[++cnt]=x%10;
        while (cnt) putchar(pr[cnt--]+'0');
    }
    template inline void writeln(tp x)
    {
        write(x);
        putchar('\n');
    }
}
using namespace FastIO;
int T,n;
int x[N];
int main()
{
    read(T);
    while(T--)
    {
        read(n);
        for(int i=1;i<=n;i++) read(x[i]);
        writeln((int)floor(sqrt(fabs(1.0 * x[n] - x[1]))));
    }
    return 0;
}

关于“多校不会题选讲(四)”我的1个想法

发表评论

电子邮件地址不会被公开。 必填项已用*标注