@happyforever 2018-10-24T13:23:57.000000Z 字数 9756 阅读 546

10.23上午解题报告

清北学堂 解题报告

各题状况

预计得分： $100+20+10$
实际得分： $100+0+0$

T1

写了俩小时。。
最开始写的做法是求逆元，判重，也就是 $O(n\log n)$ 的做法，最后快结束的时候想到用欧拉函数， $10$ 分钟飚完。
但是忘记判断 $p=1$ 的时候答案是 $0$ .

T2

T1消耗的时间太长所以就。。T2没时间了，又感觉T3以前做过，匆匆忙忙写完暴力

T3

以前做过的类似的题目询问的内容时候对每个区间 $maxn-minn$ 求和，这题是对每个区间 $maxn\times minn$ 求和，而显然 $\sum_{i=1}^{\frac{n\times (n+1)}{2}} maxn_i\times minn_i \ne \sum_{i=1}^{\frac{n\times (n+1)}{2}} maxn_i\times \sum_{i=1}^{\frac{n\times (n+1)}{2}} minn_i$

所以就不会了。。
凉凉

然后中间计算的时候还没开longlong存。。。
GG
太难受了

考场代码及题目

T1

图片.png

/*
 * 同余方程？
 *
 * 对于ax % m = b的情况，若d=gcd(m,b),d|b，那么解的个数为d
 * 对于本题，b=1,m=p,如果a与p互质那么答案多1
 * 但是无序怎么处理啊。。。
 *
 *
 */
#include <cstdio>
#include <cstring>
const int N=1e7+1;
bool flag[N];///标记数组
int phi[N],p[N],cnt=0;
void Get_phi(int n)
{
    cnt = 0;
    memset(flag, true, sizeof(flag));
    phi[1] = 1;
    for(int i=2; i<N; i++)
    {
        if(flag[i])///素数
        {
            p[cnt++] = i;
            phi[i] = i-1;///素数的欧拉函数值是素数 - 1
        }
        for(int j=0; j<cnt; j++)
        {
            if(i*p[j] > N)
                break;
            flag[i*p[j]] = false;///素数的倍数，所以i*p[j]不是素数
            if(i%p[j] == 0)///性质：i mod p == 0, 那么 phi(i * p) == p * phi(i)
            {
                phi[i*p[j]] = p[j] * phi[i];
                break;
            }
            else
                phi[i*p[j]] = (p[j]-1) * phi[i];///i mod p != 0, 那么 phi(i * p) == phi(i) * (p-1) 
        }
    }
}
int main()
{
    freopen("count.in","r",stdin);
    freopen("count.out","w",stdout);
    int p,ans=0;
    scanf("%d",&p);
    Get_phi(p);
    for(long long i=1;i<=p;++i)
        if(i*i%p==1)
            ++ans;
    printf("%d",(1ll*ans+phi[p])/2);
    fclose(stdin),fclose(stdout);
    return 0;
}
/*
int main()
{
    int p,ans=0;
    scanf("%d",&p);
    for(int i=1;i<p;++i)
    {
        if(gcd(i,p)==1)
            for(int j=i;j<p;++j)
                if(i*j%p==1)
                {
                    ++ans;
                    break;
                }
//      printf("%d\n",ans);
    }
    printf("%d",ans);
    return 0;
}*/

T2

图片.png

/*
 * 对于Subtask1可以考虑对每个点枚举是黑色或者白色
 * 对于Subtask2,由于只有两列，考虑对每一行左边是白色或者右边是白色。首先求出一共有多少行是有两个点的，而后求出有多少行只有左边点和多少行只有右边点
 */
#include <cstdio>
#include <cstring>
#include <algorithm>
const int N=1e5+1;
struct Node{
    int x,y,col;
}point[N];
int n;
inline bool cmp1(const Node &a,const Node &b)
{return a.x<b.x;}
inline bool cmp2(const Node &a,const Node &b)
{return a.y<b.y;}
inline int read()
{
    int n=0,w=1;register char c=getchar();
    while(c<'0' || c>'9'){if(c=='-')w=-1;c=getchar();}
    while(c>='0' && c<='9')n=n*10+c-'0',c=getchar();
    return n*w;
}
void dfs(int now)
{
    if(now>n)
    {
        std::sort(point+1,point+1+n,cmp1);
        int sum=0;
        for(int i=1;i<=n;++i)
        {
            if(point[i].x!=point[i-1].x)
            {
                if(sum>1 || sum<-1)return ;
                sum=0;
            }
            sum+=point[i].col;
        }
        std::sort(point+1,point+1+n,cmp2);
        for(int i=1;i<=n;++i)
        {
            if(point[i].y!=point[i-1].y)
            {
                if(sum>1 || sum<-1)return ;
                sum=0;
            }
            sum+=point[i].col;
        }
        if(sum>1 || sum<-1)return ;
        for(int i=1;i<=n;++i)
            printf("%d ",point[i].col==1?1:0);
        exit(0);
    }
    point[now].col=1;
    dfs(now+1);
    point[now].col=-1;
    dfs(now+1);
}
int main()
{
    freopen("color.in","r",stdin);
    freopen("color.out","w",stdout);
    n=read();
    for(int i=1;i<=n;++i)
        point[i]=(Node){read(),read()};
    if(n<=16)dfs(1);
    printf("-1");
    fclose(stdin),fclose(stdout);
    return 0;
}

T3

图片.png

#include <cstdio>
#include <cstring>
const int N=1e5+1,mod=998244353;
int n,a[N],sta1[N],top1,sta2[N],top2;
inline int read()
{
    int n=0,w=1;register char c=getchar();
    while(c<'0' || c>'9'){if(c=='-')w=-1;c=getchar();}
    while(c>='0' && c<='9')n=n*10+c-'0',c=getchar();
    return n*w;
}
int main()
{
    freopen("sequence.in","r",stdin);
    freopen("sequence.out","w",stdout);
    n=read();
    for(int i=1;i<=n;++i)a[i]=read();
    long long ans=0;
    for(int i=1;i<=n;++i)
    {
        top1=top2=0;
        sta1[++top1]=a[i];
        sta2[++top2]=a[i];
        ans=(ans+a[i]*a[i])%mod;
//      printf("%d\n",ans);
        for(int j=i+1;j<=n;++j)
        {
//          printf("%d %d ",i,j);
            while(top1 && sta1[top1]>a[j])--top1;
            sta1[++top1]=a[j];
            while(top2 && sta2[top2]<a[j])--top2;
            sta2[++top2]=a[j];
            ans=(ans+sta1[1]*sta2[1])%mod;
//          printf("%d %d %d\n",sta1[1],sta2[1],ans);
        }
    }
    printf("%d",ans);
    fclose(stdin),fclose(stdout);
    return 0;
}

正解及代码

T1

Subtask1

$O(p^2)$ 枚举 $x,y$ 计算，去重

Subtask2

可以发现原式就是 $x$ 在 $\mod p$ 意义下的逆元
一个数 $x$ 有逆元当且仅当 $gcd(x,p)=1$ ，若有则仅有一个
设 $1\sim p-1$ 中与 $p$ 互质的数有 $s$ 个考虑这 $s$ 个数与它
们的逆元组成的二元组，这些二元组一定符合条件，那么只要考
虑去重的问题
可以发现如果 $xy\equiv 1\pmod p,x\ne y$ ，那么 $(x,y),(y,x)$ 一定会在上述 $s$ 个二元组中各出现一次
设满足 $x^2\equiv 1\pmod p$ 的 $x$ 有 $t$ 个，可以算出 $ans=\frac{s+t}{2}$
暴力算 $p,s$ 的时间复杂度是 $O(n\log n)$ 的

Subtask3

$p=1$ 的时候。。。。有争议， $C$ 语言算出来 $0%1=0$ ,搜狗(???)算出来 $0%1=1$
$p>1$ 时 $s=\varphi(p)$
可以用线性筛求出 $s$ ，并没有卡这种操作

/*
 * 同余方程？
 *
 * 对于ax % m = b的情况，若d=gcd(m,b),d|b，那么解的个数为d
 * 对于本题，b=1,m=p,如果a与p互质那么答案多1
 * 但是无序怎么处理啊。。。
 *
 *
 */
#include <cstdio>
#include <cstring>
const int N=1e7+1;
bool flag[N];///标记数组
int phi[N],p[N],cnt=0;
void Get_phi(int n)
{
    cnt = 0;
    memset(flag, true, sizeof(flag));
    phi[1] = 1;
    for(int i=2; i<N; i++)
    {
        if(flag[i])///素数
        {
            p[cnt++] = i;
            phi[i] = i-1;///素数的欧拉函数值是素数 - 1
        }
        for(int j=0; j<cnt; j++)
        {
            if(i*p[j] > N)
                break;
            flag[i*p[j]] = false;///素数的倍数，所以i*p[j]不是素数
            if(i%p[j] == 0)///性质：i mod p == 0, 那么 phi(i * p) == p * phi(i)
            {
                phi[i*p[j]] = p[j] * phi[i];
                break;
            }
            else
                phi[i*p[j]] = (p[j]-1) * phi[i];///i mod p != 0, 那么 phi(i * p) == phi(i) * (p-1) 
        }
    }
}
int main()
{
    freopen("count.in","r",stdin);
    freopen("count.out","w",stdout);
    int p,ans=0;
    scanf("%d",&p);
    Get_phi(p);
    for(long long i=1;i<=p;++i)
        if(i*i%p==1)
            ++ans;
    printf("%d",(1ll*ans+phi[p])/2);
    fclose(stdin),fclose(stdout);
    return 0;
}
/*
int main()
{
    int p,ans=0;
    scanf("%d",&p);
    for(int i=1;i<p;++i)
    {
        if(gcd(i,p)==1)
            for(int j=i;j<p;++j)
                if(i*j%p==1)
                {
                    ++ans;
                    break;
                }
//      printf("%d\n",ans);
    }
    printf("%d",ans);
    return 0;
}*/

T2

没有无解的数据。。。

Subtask1

枚举 $O(2^n)$ 种染色方案，进行判断

Subtask2

只有两列，考虑有 $x$ 行是有两个点的， $y$ 行是左边一列有点， $z$ 行是右边一列有点
那么显然这 $x$ 行都得是一黑一白，为了应对列上的限制，这 y + z 个点的颜色可以任意调
整。
我们可以把 $x$ 行上的点的颜色调整得尽量均衡，一半行上是一白一黑，另一半行上是一黑一白。然后再调整 $y+z$ 个点

假设某点是白色对当前列有 $1$ 的贡献，黑色对当前列有 $-1$ 的贡献，那么假设 $S$ 是第一列的贡献和，若只有 $x$ 个两个点的行，那么第二列的贡献就是 $-S$

那么对剩下的 $y+z$ 个点考虑让 $S$ 依旧使构造即可

Subtask3

这一类部分分是对正解的提示

首先把坐标离散化。
考虑一个二分图，一个点 $(x,y)$ 视为在左半边的第 $x$ 个点和右半边的第 $y$ 个点之间连了一条边。
问题变成：给每条边染色，要求与每个点相连的黑边和白边的数量差小于等于 $1$ 。
由于每个点的度数都是偶数，因此一个联通块可以由一条欧拉回路覆盖。把欧拉回路上相邻的边染上不同的颜色，可以发现这样的染色方案中与每个点相连的黑边和白边的数量一定相等。

Subtask4

考虑怎样让问题变成 $Subtask3$ 。
找到一个度数为奇数的点 $u$ ，和任意一个与 $u$ 相连的点 $v$ 。
删掉 $u$ 和 $v$ 之间的边，染完剩下的图之后，再把这条边加回来。
可以发现，经过若干次删边，问题一定会变成 $Subtask3$ 。那么只要考虑把边加回来时怎么染色就可以了：
如果与 $v$ 相连的边中黑边较多，那么 $u$ 和 $v$ 之间的边染白色；否则 $u$ 和 $v$ 之间的边染黑色。

#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <map>
#include <set>
#include <queue>
#include <vector>
using namespace std;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef pair<int, int> PII;
#define fi first
#define se second
#define MP make_pair
int read()
{
    int v = 0, f = 1;
    char c = getchar();
    while (c < 48 || 57 < c) {if (c == '-') f = -1; c = getchar();}
    while (48 <= c && c <= 57) v = (v << 3) + v + v + c - 48, c = getchar();
    return v * f;
}
const int N = 2001000;
int init[N], a[N], b[N], c[N], d[N], n, len, ans[N], x[N], X[N], y[N], Y[N], vis[N];
map<int, int> mp[N];
set<int> S;
struct Edge
{
    int nxt, to, val;
    Edge(int _nxt = 0, int _to = 0, int _val = 0)
    {
        nxt = _nxt;
        to = _to;
        val = _val;
    }
} eg[N << 1];
int head[N], en = 1;
void set_edge(int u, int v, int w)
{
    eg[++en] = Edge(head[u], v, w);
    head[u] = en;
}
void dfs(int u)
{
    for (int e = head[u]; e; e = head[u])
    {
        head[u] = eg[e].nxt;
        if (vis[e / 2]) continue;
        vis[e / 2] = 1;
        int v = eg[e].to;
        dfs(v);
        d[++d[0]] = eg[e].val;
    }
}
int main()
{
    freopen("color.in", "r", stdin);
    freopen("color.out", "w", stdout);
    n = read();
    for (int i = 1; i <= n; i++)
    {
        x[i] = X[i] = read();
        y[i] = Y[i] = read();
    }
    sort(X + 1, X + n + 1);
    sort(Y + 1, Y + n + 1);
    X[0] = unique(X + 1, X + n + 1) - X - 1;
    Y[0] = unique(Y + 1, Y + n + 1) - Y - 1;
    for (int i = 1; i <= n; i++)
    {
        x[i] = lower_bound(X + 1, X + X[0] + 1, x[i]) - X;
        y[i] = lower_bound(Y + 1, Y + Y[0] + 1, y[i]) - Y + X[0];
        mp[x[i]][y[i]] = i;
        mp[y[i]][x[i]] = i;
    }
    for (int i = 1; i <= X[0] + Y[0]; i++)
        if (mp[i].size() & 1)
            S.insert(i);
    while (!S.empty())
    {
        int u = *S.begin();
        int v = (*mp[u].begin()).fi;
        a[++len] = mp[u][v];
        b[len] = u;
        c[len] = v;
        mp[u].erase(v);
        mp[v].erase(u);
        S.erase(u);
        if (mp[v].size() & 1)
            S.insert(v);
        else
            S.erase(v);
    }
    for (int i = 1; i <= X[0]; i++)
        for (map<int, int> :: iterator j = mp[i].begin(); j != mp[i].end(); j++)
        {
            set_edge(i, (*j).fi, (*j).se);
            set_edge((*j).fi, i, (*j).se);
        }
    for (int i = 1; i <= X[0] + Y[0]; i++)
        if (head[i])
            dfs(i);
    for (int i = 1; i <= d[0]; i++)
    {
        ans[d[i]] = i & 1;
        if (i & 1)
        {
            init[x[d[i]]]--;
            init[y[d[i]]]--;
        } else
        {
            init[x[d[i]]]++;
            init[y[d[i]]]++;
        }
    }
    for (int i = len; i >= 1; i--)
    {
        int u = b[i], v = c[i];
        if (init[v] > 0)
        {
            init[v]--;
            init[u]--;
            ans[a[i]] = 1;
        } else
        {
            init[v]++;
            init[u]++;
            ans[a[i]] = 0;
        }
    }
    for (int i = 1; i <= n; i++)
        printf("%d ", ans[i]);
    puts("");
}

T3

开long long！开long long！开long long！

Subtask1

$O(n^2)$ 枚举每个区间，怎么维护最大最小值随意

Subtask2

分治。如果当前是在考虑区间 [l; r] 的子区间的价值和，设区间 $[l,r]$ 内最大值的下标为 $mid$ 。
考虑左端点在 $[l,mid]$ 内，右端点在 $[mid,r]$ 内的区间的价值和。它们内部的最大值是 $amid$ 。
对 $[l,mid]$ 做后缀 $min$ ，对 $[mid,r]$ 做前缀 $min$ ，不妨把结果记为 $mn[i]$ 。即 $l\le i\le mid$ 时， $mn[i]=\min_{i=l}^{mid} a_i$ ； $mid\lt i\le r$ 时， $mn[i]=min_{i=mid}^r a_i$ 。
枚举左端点 $i$ ，由于右半部分的 $mn$ 是单调的，一定存在一个分界点 $p$ ，使得 $j\le p$ 时 $mn[j]\ge mn[i]$ ， $j\gt p$ 时 $mn[j]\lt mn[i]$ 。
又由于左半部分的 $mn$ 也是单调的，所以左端点 $i$ 移动时，分界点 $p$ 的移动方向是不变的。这样就容易对每个左端点 $i$ 都求出分界点 $p$ 了。另外再求出 $mn$ 的前缀和，就能 $O(1)$ 求出左端点在 $i$ ，右端点在 $[mid,r]$ 内的区间的价值和了。
然后再递归计算区间 $[l,mid-1]$ 和 $[mid+1,r]$ 。
总复杂度 $O(n\log n)$ 。

Subtask3

只有 $10$ 种数，因此左端点固定时，最大值至多只有 $10$ 种，即右端点在某段区间内的最大值相同，而这种区间最多只有 $10$ 个。
最小值同理。同时考虑最大值和最小值可以知道，左端点固定时，右端点在某段区间内的最大值和最小值都相同，而这种区间最多只有 $20$ 个。
移动左端点，用单调栈维护这些区间。复杂度 $O(n\times 20)$ 。

Subtask4

标算是 $O(n\log n)$ 的

$O(n\log n)$ 的做法应该有许多种，这里只讲一种。
跟 $Subtask2$ 的做法类似，每次取 $mid=\lfloor l+2r\rfloor$ ，对最大值进行和最小值类似的操作（不妨把前缀/后缀 $max$ 的结果记为 $mx[i]$ ，我们可以求出最大值的分界点 $q$ 。除了 $mn$ 的前缀和外，再求出 $mx$ 的前缀和以及 $mn\times mx$ 的前缀和。 $p$ 和 $q$ 把右半部分划分成三个区间，对三个区间分别计算。利用求出来的前缀和可以 $O(1)$ 算出右端点在一个区间内的价值和。
然后再递归计算左右两半部分。

#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <map>
#include <set>
#include <queue>
#include <vector>
using namespace std;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef pair<int, int> PII;
#define fi first
#define se second
#define MP make_pair
int read()
{
    int v = 0, f = 1;
    char c = getchar();
    while (c < 48 || 57 < c) {if (c == '-') f = -1; c = getchar();}
    while (48 <= c && c <= 57) v = (v << 3) + v + v + c - 48, c = getchar();
    return v * f;
}
const int N = 1001000;
const ll MOD = 998244353;
int n, a[N], mn[N], mx[N], s1[N], s2[N], s3[N], ans;
void work(int l, int r)
{
    if (l == r)
    {
        ans = (ans + 1LL * a[l] * a[l] % MOD) % MOD;
        return ;
    }
    int mid = l + r >> 1;
    mn[mid] = a[mid];
    for (int i = mid - 1; i >= l; i--)
        mn[i] = min(mn[i + 1], a[i]);
    mx[mid] = a[mid];
    for (int i = mid - 1; i >= l; i--)
        mx[i] = max(mx[i + 1], a[i]);
    mn[mid + 1] = a[mid + 1];
    for (int i = mid + 2; i <= r; i++)
        mn[i] = min(mn[i - 1], a[i]);
    mx[mid + 1] = a[mid + 1];
    for (int i = mid + 2; i <= r; i++)
        mx[i] = max(mx[i - 1], a[i]);
    s1[mid] = 0;
    for (int i = mid + 1; i <= r; i++)
        s1[i] = (s1[i - 1] + mn[i]) % MOD;
    s2[mid] = 0;
    for (int i = mid + 1; i <= r; i++)
        s2[i] = (s2[i - 1] + mx[i]) % MOD;
    s3[mid] = 0;
    for (int i = mid + 1; i <= r; i++)
        s3[i] = (s3[i - 1] + 1LL * mn[i] * mx[i] % MOD) % MOD;
    int p1 = mid + 1, p2 = mid + 1;
    for (int i = mid; i >= l; i--)
    {
        while (p1 <= r && mn[p1] > mn[i]) p1++;
        while (p2 <= r && mx[p2] < mx[i]) p2++;
        if (p1 < p2)
        {
            ans = (ans + 1LL * mn[i] * mx[i] % MOD * (p1 - mid - 1) % MOD) % MOD;
            ans = (ans + 1LL * mx[i] * (s1[p2 - 1] - s1[p1 - 1] + MOD) % MOD) % MOD;
            ans = (ans + (s3[r] - s3[p2 - 1] + MOD) % MOD) % MOD;
        } else
        {
            ans = (ans + 1LL * mn[i] * mx[i] % MOD * (p2 - mid - 1) % MOD) % MOD;
            ans = (ans + 1LL * mn[i] * (s2[p1 - 1] - s2[p2 - 1] + MOD) % MOD) % MOD;
            ans = (ans + (s3[r] - s3[p1 - 1] + MOD) % MOD) % MOD;
        }
    }
    work(l, mid);
    work(mid + 1, r);
}
int main()
{
    freopen("sequence.in", "r", stdin);
    freopen("sequence.out", "w", stdout);
    n = read();
    for (int i = 1; i <= n; i++)
        a[i] = read();
    work(1, n);
    printf("%d\n", ans);
}

10.23上午解题报告

各题状况

T1

T2

T3

考场代码及题目

T1

T2

T3

正解及代码

T1

Subtask1

Subtask2

Subtask3

T2

Subtask1

Subtask2

Subtask3

Subtask4

T3

Subtask1

Subtask2

Subtask3

Subtask4

内容目录

选择主题