上午

T1 np

解析：打表出所有k!，其中k mod 10000000=0。询问时直接找到已知的答案，并计算不超过10000000就能找到答案。

T2 program

解析：先将ai进行排序。

令f[i]表示1~i中相同的ai对数。

对于所有ai!=a{i+1}的位置，将f[i]*g*(g-1)/2累加进答案中。其中g表示存在多少数字=a{i+1}。

时间复杂度nlogn。

T3 select

解析：假设我们选了x行，那么必然选择了k-x列。

令f[i]表示选择i行得到的最大和。考虑怎么求出所有f[i]。

这个是显然可以贪心的。记录所有行的总和。利用大根对维护即可。

令g[i]表示选择i列得到的最大和。

已知f与g后。

答案为max{f[i]+g[k-i]-i*(k-i)*p)。

下午

T1 chocolate

解析：

解法1：如果一个数x是2的幂次，那么能得到的快乐值为x-1。

因此我们可以把n拆成若干2的幂次，计算快乐值之和即可。

解法2：ans=n-c(n) {c(n)表示n这个数的二进制形式上有多少个1}

T2 run

解析：二分答案，对于那些不能被到达的位置设置为障碍，问题转换成判断连通性问题

，并查集或者搜索都可以。

另外最短路也可以做。

T3 cactus

解析：观察美丽的仙人掌的定义，发现编号为i与i+1之间必存在一条边，问题转化成有

若干区间，求最多的区间，使得区间之间没有重叠和覆盖。这个问题是可以直接

贪心或者dp的。

上午

T1代码：

#include
     
      #define name "np"#define ll long longusing namespace std;const int a[101]={
   0,682498929,491101308,76479948,723816384,67347853,27368307,625544428,199888908,888050723,927880474,281863274,661224977,623534362,970055531,261384175,195888993,66404266,547665832,109838563,933245637,724691727,368925948,268838846,136026497,112390913,135498044,217544623,419363534,500780548,668123525,128487469,30977140,522049725,309058615,386027524,189239124,148528617,940567523,917084264,429277690,996164327,358655417,568392357,780072518,462639908,275105629,909210595,99199382,703397904,733333339,97830135,608823837,256141983,141827977,696628828,637939935,811575797,848924691,131772368,724464507,272814771,326159309,456152084,903466878,92255682,769795511,373745190,606241871,825871994,957939114,435887178,852304035,663307737,375297772,217598709,624148346,671734977,624500515,748510389,203191898,423951674,629786193,672850561,814362881,823845496,116667533,256473217,627655552,245795606,586445753,172114298,193781724,778983779,83868974,315103615,965785236,492741665,377329025,847549272,698611116};const int mod=1e9+7;const int sz=1e7;ll n,p;ll ans=1;int main(){    freopen(name".in","r",stdin);    freopen(name".out","w",stdout);    scanf("%I64d%I64d",&n,&p);    if(n>=p){puts("0");return 0;}    if(p==mod){
   //分段打表         n

T2代码：

//代码优化 O(n)算法#include
     
      #include
      
       #define ll long longusing namespace std;const int N=1e5+10;const ll mod=1e9+7;int n,a[N];ll ans,f[N],sum;#define name "program"int main(){    freopen(name".in","r",stdin);    freopen(name".out","w",stdout);    scanf("%d",&n);    for(int i=1;i<=n;i++) scanf("%d",a+i);    sort(a+1,a+n+1);    sum=1;f[1]=1;    for(int i=2;i<=n;i++){        f[i]=f[i-1];        if(a[i]==a[i-1]){            f[i]=f[i]-sum*sum;sum++;            f[i]=f[i]+sum*sum;            f[i]%=mod;        }        else{            sum=1;f[i]++;        }    }    sum=0;    for(int i=n;i>1;i--){        if(a[i]==a[i+1]) sum++;else sum=1;        if(a[i]!=a[i-1]) ans=(ans+f[i-1]*sum%mod*sum)%mod;    }    printf("%d",(int)ans);    fclose(stdin);     fclose(stdout);     return 0;}

T3代码：

//大根堆+前缀和 贪心#include
     
      //#include
      
       #include
       
        #define ll long longusing namespace std;const int N=1e6+10;int n,m,k,p;ll ans,s1[N],s2[N],p1[N],p2[N];//priority_queue
        
         q1,q2;#define name "select" int main(){    freopen(name".in","r",stdin);    freopen(name".out","w",stdout);    scanf("%d%d%d%d",&n,&m,&k,&p);    for(int i=1,t;i<=n;i++){        for(int j=1;j<=m;j++){            scanf("%d",&t);            s1[i]+=t;            s2[j]+=t;        }    }    make_heap(s1+1,s1+n+1);    make_heap(s2+1,s2+m+1);    for(int i=1,t;i<=k;i++){        p1[i]=p1[i-1]+s1[1];        pop_heap(s1+1,s1+n+1);        s1[n]-=p*m;        push_heap(s1+1,s1+n+1);        p2[i]=p2[i-1]+s2[1];        pop_heap(s2+1,s2+m+1);        s2[m]-=p*n;        push_heap(s2+1,s2+m+1);    }    /*用优先队列实现好像有点问题     for(int i=1;i<=n;i++) q1.push(s1[i]);    for(int i=1;i<=m;i++) q2.push(s2[i]);    for(int i=1,t;i<=k;i++){        t=q1.top();q1.pop();        p1[i]=p1[i-1]+t;        s1[n]-=p*m;        q1.push(s1[n]);        t=q2.top();q2.pop();        p2[i]=p2[i-1]+t;        s2[m]-=p*n;        q2.push(s2[m]);    }*/    ll ans=-1e15;    for(ll i=0;i<=k;i++) ans=max(ans,p1[i]+p2[k-i]-i*(k-i)*p);    printf("%I64d",ans);    return 0;}/*60分骗分代码存档 #include
         
          #include
          
           #include
           
            #define name "select"#define ll long long#ifdef unix#define LL "%lld"#else#define LL "%I64d"#endifusing namespace std;inline const ll read(){ register ll x=0,f=1; register char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();} return x*f;}const ll N=1e3+10;ll a[N][N];ll s1[N][N],s2[N][N];ll n,m,k,p,sans,ans;ll px,py;priority_queue
            
             q;int main(){ //freopen("sh.txt","r",stdin); freopen(name".in","r",stdin); freopen(name".out","w",stdout); n=read();m=read();k=read();p=read(); for(ll i=1;i<=n;i++){ for(ll j=1;j<=m;j++){ a[i][j]=read(); } } for(ll i=1;i<=n;i++){ for(ll j=1;j<=m;j++){ s1[i][j]=s1[i][j-1]+a[i][j]; s2[i][j]=s2[i-1][j]+a[i][j]; } } if(k==1){ for(ll i=1;i<=n;i++) ans=max(ans,s1[i][m]); for(ll i=1;i<=m;i++) ans=max(ans,s2[n][i]); printf(LL,ans); return 0; } if(p==0){ for(ll i=1;i<=n;i++) ans=max(ans,s1[i][m]); for(ll i=1;i<=m;i++) ans=max(ans,s2[n][i]); printf(LL,k*ans); return 0; } if(n==1){ for(ll i=1;i<=m;i++) q.push(a[1][i]); for(ll i=1,t;i<=k;i++){ t=q.top();q.pop(); ans+=t; q.push(t-p); } printf(LL,ans); } if(n<=5&&m<=5&&k<=5){ while(k--){ for(ll i=1;i<=n;i++){ for(ll j=1;j<=m;j++){ s1[i][j]=s1[i][j-1]+a[i][j]; s2[i][j]=s2[i-1][j]+a[i][j]; } } ans=-0x3f3f3f3f; for(ll i=1;i<=n;i++){ if(ans

下午

T1代码：

#include
     
      using namespace std;int n,cpy,Cn;#define name "chocolate"int main(){    freopen(name".in","r",stdin);    freopen(name".out","w",stdout);    scanf("%d",&n);    cpy=n;    for(;n;n>>=1) if(n&1) Cn++;    printf("%d",cpy-Cn);    fclose(stdin);    fclose(stdout);    return 0;}/*原始100分代码存档#include
      
       #define name "chocolate"#define ll long long#ifdef unix#define LL "%lld"#else#define LL "%I64d"#endifusing namespace std;int n;ll tot;void dfs(ll n){    ll i,m=1;    if(!n||n==1) return ;    for(i=1;;i++){        m=1<
       
        n) break;    }    m=1LL<<(i-1);    tot+=m-1;    dfs(n-m);}int main(){    freopen(name".in","r",stdin);    freopen(name".out","w",stdout);    scanf(LL,&n);    dfs(n);    printf(LL"\n",tot);    return 0;}*/

T2代码：

#include
     
      using namespace std;const int N=1e6+10;const int M=1e3+1;int n,m,cnt,d[M][M],a[M][M],p[M][M],sx[N],sy[N],fa[N];const int dx[4]={
   0,0,1,-1};const int dy[4]={
   1,-1,0,0};inline bool inside(int x,int y){    return x>0&&x<=n&&y>0&&y<=m;}int find(int x){    return fa[x]==x?x:fa[x]=find(fa[x]);}bool check(int x){    for(int i=1;i<=cnt;i++) fa[i]=i;    for(int i=1;i<=n;i++){        for(int j=1;j<=m;j++){            if(d[i][j]>=x){                for(int nx,ny,k=0;k<=4;k++){                    nx=i+dx[k];                    ny=j+dy[k];                    if(inside(nx,ny)&&d[nx][ny]>=x){                        fa[find(p[i][j])]=find(p[nx][ny]);                    }                }            }        }    }    return find(p[1][1])==find(p[n][m]);}int l,r,mid,ans;#define name "run"int main(){    freopen(name".in","r",stdin);    freopen(name".out","w",stdout);    scanf("%d%d",&n,&m);    for(int i=1;i<=n;i++){        for(int j=1;j<=m;j++){            scanf("%d",&a[i][j]);            if(a[i][j]){                sx[++r]=i;sy[r]=j;                d[i][j]=1;            }        }    }    int px,py;    while(l!=r){        px=sx[++l];py=sy[l];        for(int nx,ny,i=0;i<4;i++){            nx=px+dx[i];            ny=py+dy[i];            if(inside(nx,ny)&&!d[nx][ny]){                d[nx][ny]=d[px][py]+1;                sx[++r]=nx;sy[r]=ny;            }        }    }    for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) p[i][j]=++cnt;    l=0;r=1e6;    while(l<=r){        mid=l+r>>1;        if(check(mid)) ans=mid,l=mid+1;        else r=mid-1;    }    printf("%d",ans-1);    fclose(stdin);    fclose(stdout);    return 0;}

T3代码：

#include
     
      #include
      
       using namespace std;const int N=1e5+10;int n,m,g[N],f[N];#define name "cactus"int main(){    freopen(name".in","r",stdin);    freopen(name".out","w",stdout);    scanf("%d%d",&n,&m);    for(int i=1,x,y;i<=m;i++){        scanf("%d%d",&x,&y);        if(x>y) swap(x,y);        if(x+1==y) continue;        g[y]=max(g[y],x);    }    f[0]=-1;    for(int i=2;i<=n;i++) f[i]=max(f[i-1],f[g[i]]+1);    printf("%d",f[n]+n-1);    fclose(stdin);    fclose(stdout);    return 0;}