多校不水题选讲(二)

emmm,day2的多校突然变难。。。然后我们只切了三题都有100名。。。

好的吧,我们先来讲一道特别诡异的题目。。。

T5:Hack It

dls表示这道题水得一批。。。。被虐了。。。

题目是要求你输出一个只有零一的方阵,其中没有一个子矩阵四个角都是一,同时方阵的长在2000以内,一的数量不少于85000。。。

看到题目,我先懵逼了,去想有什么构造方法。。。直到把横杠斜杠什么都pass掉。。。然后到死没写出来。。。之后看了dls讲题,豁然开朗。。。

我们先找到一个质数p,p的平方大于2000,p=47。。。然后我们把每一行分成一份一份。。。每份47个(多出来的先别管)。。。

我们先来看当p=5时的构造方法。。。

第一行:10000 10000 10000 10000 10000;

第二行:10000 01000 00100 00010 00001;

第三行:10000 00100 00001 01000 00010;

第四行:10000 00010 01000 00001 00100:

第五行:10000 00001 00010 00100 01000:

我们发现第一行的每一个1在一组内的位置没变,第二行每一组的1比上一组的多后移了一位。。。第三组两位。。。这么看来第 i 行的每一组的1都比上一组后移 i-1 位。。。

我们已经知道构造方法了,那么会发现这里只有5行,当p=47时,也才47行,达不到2000,怎么办呢,这时我们就用到了一个高深莫测的方法,把上47行的每一个1向后移一位(组内循环),然后放到下面来。。。易得这样没有一个子矩形四个角都是1。。。然后我们就巧妙的A了。。。

代码:

#include<bits/stdc++.h>
#define LL long long
using namespace std;
const LL N=1e4+10;
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;
main()
{
    int n=2000,flag=1;printf("2000\n");
    for(int i=0;i<2000;i++)
    {
        flag=i/47;
        for(int j=0;j<2000;j++)
        {
            if(j==flag)
            {
                printf("1");
                flag=flag+47-flag%47+(flag%47+i)%47;
            }
            else printf("0");   
        }
        printf("\n");
    }
    return 0;
}

T4:Game

题意:

给你一个数n,每次一个人可以取走一个数k和它的所有因子。。。问先手是否有必胜策略。。。

分析:

易得,必胜策略总会存在。。。那我们考虑,假如先手有必胜策略,输出“Yes”,否则我们取1,这时后手必胜相当于后手变成先手,所以先手获胜,输出“Yes”

代码:

#include<bits/stdc++.h>
using namespace std;
int main()
{
    for(int n;~scanf("%d",&n);)
        puts("Yes");
    return 0;
}

T3:Cover

题意:给你一个无向图,问最少几笔画完。。。输出路径。。。

分析,我们一直如果图上点的度数都为偶数或有两个为奇数,那么满足欧拉回路,可以直接跑欧拉回路。。。否则,我们在两个奇数节点之间连一条假边,然后跑欧拉回路,再去掉假边就好了。。。

代码:

 

#include<bits/stdc++.h>
#define LL long long
using namespace std;
const LL N=1e5+10;
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;
struct Edge
{
    int to, next;
    bool able;
} edge[N * 4];
int n, m, degree[N], head[N], cnt, res;
bool vis[N];
vector st;
vector anss[N];
void add(int u, int v)
{
    edge[++cnt].next = head[u];
    edge[cnt].to = v;
    edge[cnt].able = true;
    head[u] = cnt;
    ++degree[u];
}
inline void add_edge(int u, int v){add(u, v),add(v, u);}
void dfs(int now)
{
    vis[now] = true;
    if (degree[now] & 1)
        st.push_back(now);
    for (int i = head[now]; i; i = edge[i].next)
        if (!vis[edge[i].to])
            dfs(edge[i].to);
}
void dfs_ans(int now)
{
    for (int i = head[now]; i; i = edge[i].next)
        if (edge[i].able)
        {
            edge[i].able = edge[i ^ 1].able = false;
            dfs_ans(edge[i].to);
            if (i > 2 * m + 1) ++res;
            else anss[res].push_back(i / 2 * (2 * (i & 1) - 1));
        }
}
int main()
{
    while(~scanf("%d%d",&n,&m))
    {
        cnt = 1, res = 0;
        for (int i = 0,u,v; i < m; ++i)
        {
            scanf("%d %d", &u, &v);
            add_edge(u, v);
        }
        for (int i = 1; i <= n; ++i)
        {
            if (!vis[i] and degree[i])
            {
                dfs(i);
                if (st.empty())
                {
                    st.push_back(i);
                    st.push_back(i);
                }
                for (int j = 2; j < st.size(); j += 2)
                    add_edge(st[j], st[j + 1]);
                res++;
                dfs_ans(st[0]);
                st.clear();
            }
        }
        printf("%d\n", res);
        for (int i = 1; i <= res; ++i)
        {
            printf("%d", anss[i].size());
            for (int j = 0; j < anss[i].size(); ++j)
                printf(" %d", anss[i][j]);
            puts("");
            anss[i].clear();
        }
        for (int i = 1; i <= n; ++i)
        {
            vis[i] = false;
            head[i] = 0;
            degree[i] = 0;
        }
    }
    return 0;
}

发表评论

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