这次又炸了两道题。。410变270。。

T3 dfs之后没恢复数组，T4 这次才知道string::erase的复杂度是$O(n)$。。

T2

description：

最近小G新开了一家蛋糕店。开业第一天，一共来个n位顾客。由于小G非常懒，他每次只会接待一位顾客。每个顾客都想尽快的买到蛋糕，所以没有第一个买到蛋糕的顾客都会有一个愤怒值。最终排在第i个位置的顾客x的愤怒值为i*a[x]。小G想要所有顾客的愤怒值之和最小。求最小的愤怒值之和。

签到题。。。

排个序后输出$sigma{i=1}{n}{a[i]*(i-1)}$即可

std:

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<ctime>
#include<vector>
#include<queue>
#include<algorithm>
#include<string>
#include<sstream>
#include<cctype>
#include<cmath>
#include<iomanip>
#include<map>
#include<stack>
#include<set>
#include<functional>
#define in(x) x=read()
#define qr read()
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
inline ll read()
{
    char ch=' ';
    ll f=1,x=0;
    while(!isdigit(ch)){ch=getchar();if(ch=='-')f*=-1;}
    while(isdigit(ch)){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
    return f*x;
}
bool cmp(int x,int y){return x>y;}
ll a[1000010],ans=0;
int main()
{
    freopen("cake.in","r",stdin);
    freopen("cake.out","w",stdout);
    ll n=qr;
    for(int i=1;i<=n;i++)in(a[i]);
    sort(a+1,a+1+n,cmp);
    for(int i=1;i<=n;i++)ans+=ll(i-1)*a[i];
    cout<<ans;
    return 0;
}

T3

description:

小G通过摆放一些城市和道路构成了一个世界地图。趁着小G出去玩的时候，大G把小G的世界地图上的城市全部打乱并放在了原来这些城市所在的位置（并不是一一对应），又修改了一些道路。小G玩完回来后发现自己的东西被打乱了，感到非常生气，但是他又被一个更有趣的问题吸引了：被修改之后的世界地图与原来的世界地图的最大相似度是多少？ （ps：相似度的定义为将城市还原后还有多少条道路和之前的道路相同）

$9!*500$暴搜即可

然而这题有许多坑。。

有重边。。。加边时要用++，不能用=1。。

另外check完后要把邻边矩阵还原（这个值90分。。。）

std:

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<ctime>
#include<vector>
#include<queue>
#include<algorithm>
#include<string>
#include<sstream>
#include<cctype>
#include<cmath>
#include<iomanip>
#include<map>
#include<stack>
#include<set>
#include<functional>
#define in(x) x=read()
#define qr read()
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
inline int read()
{
    char ch=' ';
    int f=1,x=0;
    while(!isdigit(ch)){ch=getchar();if(ch=='-')f*=-1;}
    while(isdigit(ch)){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
    return f*x;
}
int ans[10],vis[10],anss=0,m,n,a[510],b[510],c[510],d[510],e[10][10],f[10][10];
void check()
{
    int res=0;
    for(int i=1;i<=m;i++)
    {
        if(e[ans[c[i]]][ans[d[i]]])res++,e[ans[c[i]]][ans[d[i]]]--;
    }
    for(int i=1;i<=9;i++)
    {
        for(int j=1;j<=9;j++)
        {
            e[i][j]=f[i][j];
        }
    }
    anss=max(anss,res);
}
void dfs(int x)
{
    if(x>n)
    {
        check();
        return;
    }
    for(int i=1;i<=n;i++)
    {
        if(!vis[i])
        {
            ans[x]=i;
            vis[i]=1;
            dfs(x+1);
            ans[x]=vis[i]=0;
        }
    }
}
int main()
{
    freopen("similarity.in","r",stdin);
    freopen("similarity.out","w",stdout);
    in(n),in(m);
    for(int i=1;i<=m;i++)in(a[i]),in(b[i]),e[a[i]][b[i]]++;
    for(int i=1;i<=m;i++)in(c[i]),in(d[i]);
    for(int i=1;i<=9;i++)
    {
        for(int j=1;j<=9;j++)
        {
            f[i][j]=e[i][j];
        }
    } 
    dfs(1);
    cout<<anss;
    return 0;
}

T4

description：

小G最近学会了二进制数，他觉得太小的二进制数太没意思，于是他想对一个巨大二进制数做以下4种基础运算： 运算1：将整个二进制数加1 运算2：将整个二进制数减1 运算3：将整个二进制数乘2 运算4：将整个二进制数整除2 小G很想知道运算后的结果，他只好向你求助。 （Ps：为了简化问题，数据保证+，-操作不会导致最高位的进位与退位）

直接模拟。。。

然而直接用了string，结果string::erase是o(n)。。。T掉50分

而且这样实际上通不过。。

（如果1100000...,然后不断+1-1+1-1。。。复杂度就炸了）

正解：

存两个高精度x,y，开始x=输入，y=0

+：x++

-：y++

$*：x*=2,y*=2$

/：如果y末尾为0先y++，然后x/=2,y/=2

最后输出x-y即可

std：

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<ctime>
#include<vector>
#include<queue>
#include<algorithm>
#include<string>
#include<sstream>
#include<cctype>
#include<cmath>
#include<iomanip>
#include<map>
#include<stack>
#include<set>
#include<functional>
#define in(x) x=read()
#define qr read()
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
inline int read()
{
    char ch=' ';
    int f=1,x=0;
    while(!isdigit(ch)){ch=getchar();if(ch=='-')f*=-1;}
    while(isdigit(ch)){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
    return f*x;
}
int s1[7000010]={0},s2[7000010]={0},ss1[7000010]={0},ss2[7000010]={0};
int main()
{
    freopen("two.in","r",stdin);
    freopen("two.out","w",stdout);
    int n1=qr+700000-1,m=qr;
    for(int i=700000;i<=n1;i++)s1[i]=getchar()-'0';
    int n2=700000,l1=700000,l2=700000;
    char op=' ';
    for(int i=1;i<=m;i++)
    {
        op=getchar();
        while(op!='+'&&op!='-'&&op!='*'&&op!='/')op=getchar();
        if(op=='/')
        {
            if(s2[n2]==1&&s1[n1]==0)
            {
                s2[n2]++;
                int now=n2;
                while(s2[now]>=2)
                {
                    s2[now]=0;
                    now--;
                    s2[now]++;
                    if(now<l2)l2--;
                }
            }
            n1--,n2--;
            if(n2<l2)l2--;
        }
        if(op=='*'){s1[++n1]=0,s2[++n2]=0;}
        if(op=='+')
        {
            s1[n1]++;
            int now=n1;
            while(s1[now]>=2)
            {
                s1[now]=0;
                now--;
                s1[now]++;
                if(now<l1)l1--;
            }
        }
        if(op=='-')
        {
            s2[n2]++;
            int now=n2;
            while(s2[now]>=2)
            {
                s2[now]=0;
                now--;
                s2[now]++;
                if(now<l2)l2--;
            }
        }
    }
    for(int i=1;i<=n1-l1+1;i++)ss1[n1-l1+2-i]=s1[i+l1-1];
    for(int i=1;i<=n2-l2+1;i++)ss2[n2-l2+2-i]=s2[i+l2-1];
    int y1=n1-l1+1,y2=n2-l2+1;
    for(int i=1;i<=y2;i++)
    {
        ss1[i]-=ss2[i];
        if(ss1[i]<0)ss1[i]+=2,ss1[i+1]--;
    }
    int now=y2+1;
    while(ss1[now]<0)ss1[now]+=2,ss1[now+1]--,now++;
    if(ss1[y1]<0)y1--;
    for(int i=y1;i>=1;i--)cout<<ss1[i];
    return 0;
}

T5

description：

小 X 最近迷上了矩阵，他定义了一个对于一种特殊矩阵的特征函数 G。对于 N*N 的矩
阵 A， A 的所有元素均为 0 或 1，则 G(A)等于所有 A[i][j]*A[j][i](1<=i,j<=n)的和对 2 取余之
后的结果。举一个例子：
对于上图这个 3*3 矩阵 A， G(A)=(1*1+1*0+1*1+0*1+1*1+1*0+1*1+ 0*1+0*0) mod 2=0
当然询问一个矩阵的 G 值实在是太简单了。小 X 在给出一个 N*N 矩阵的同时将给你 Q
个操作，操作描述如下：
操作 1：形如一个整数 1 和一个整数 x，表示将第 x 行的元素全部“翻转”。
操作 2：形如一个整数 2 和一个整数 x，表示将第 x 列的元素全部“翻转”。
操作 3：形如一个整数 3，表示询问当前矩阵的特征值 G。
“翻转”的定义为将 1 变成 0，将 0 变成 1。

虽然在T5，但是很水。。

只有对角线上的点才对答案有贡献，所以每次修改ans必定0变1或1变0

所以每次ans=1-ans，最终输出ans即可

std：

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<ctime>
#include<vector>
#include<queue>
#include<algorithm>
#include<string>
#include<sstream>
#include<cctype>
#include<cmath>
#include<iomanip>
#include<map>
#include<stack>
#include<set>
#include<functional>
#define in(x) x=read()
#define qr read()
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
inline int read()
{
    char ch=' ';
    int f=1,x=0;
    while(!isdigit(ch)){ch=getchar();if(ch=='-')f*=-1;}
    while(isdigit(ch)){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
    return f*x;
}
int a[1010][1010],n,ans=0;
int main()
{
    freopen("matrix.in","r",stdin);
    freopen("matrix.out","w",stdout);
    in(n);
    int q=qr;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            in(a[i][j]);
            if(i==j)ans+=a[i][j]*a[i][j],ans%=2;
        }
    }
    for(int i=1;i<=q;i++)
    {
        int op=qr;
        if(op==3)cout<<ans;
        else qr,ans=1-ans;
    }
    return 0;
}

T1

description：

小G在一个n*m的棋盘上随意放上了一些黑色的棋子，然后又在剩下所有没有放棋子的格子里放上了白色的棋子。现在小G想知道他是否能通过以下两种变换将整个棋盘上的棋子全部变成白色。 变幻1：选择一列，将这一列的棋子全部反色，即黑变白，白变黑。 变幻2：选择一行，将这一行的棋子全部反色。 如果能将整个棋盘上的棋子全部变成白色，则输出最少需要的变幻次数。否则输出经过若干次变幻后，棋盘上最少的黑子个数。

对，你没看错，就是T1

这题虽然实际不难，但很难想，放在这里才是真实难度（考试时这题直接弃疗。。）

主要就是要发现每行最多只能反色一次，然后枚举行，贪心列即可

std：

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<ctime>
#include<vector>
#include<queue>
#include<algorithm>
#include<string>
#include<sstream>
#include<cctype>
#include<cmath>
#include<iomanip>
#include<map>
#include<stack>
#include<set>
#include<functional>
#define in(x) x=read()
#define qr read()
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
inline int read()
{
    char ch=' ';
    int f=1,x=0;
    while(!isdigit(ch)){ch=getchar();if(ch=='-')f*=-1;}
    while(isdigit(ch)){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
    return f*x;
}
int anss1=10000000,anss2=10000000,b[1010][1010],a[1010][1010];
int main()
{
    freopen("chess.in","r",stdin);
    freopen("chess.out","w",stdout);
    int n=qr,m=qr;
    bool f=0;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            b[i][j]=getchar()-'0';
        }
        getchar();
    }
    for(int i=0;i<(1<<n);i++)
    {
        int ans1=0,ans2=0;
        for(int j=1;j<=n;j++)
        {
            for(int k=1;k<=m;k++)a[j][k]=b[j][k];
        }
        for(int j=1;j<=n;j++)
        {
            if(i&(1<<j))
            {
                ans1++;
                for(int k=1;k<=m;k++)
                {
                    a[j][k]^=1;
                }
            }
        }
        for(int j=1;j<=m;j++)
        {
            int sum=0;
            for(int k=1;k<=n;k++)
            {
                if(a[k][j])sum++;
            }
            if(sum*2>n)ans1++,ans2+=(n-sum);
            else ans2+=sum;
        }
        if(ans2==0)anss1=min(anss1,ans1),f=1;
        else anss2=min(anss2,ans2);
    }
    if(f)cout<<anss1;
    else cout<<anss2;
    return 0;
}