# AOGC2020赛季1讲评

### 第一场比赛：

1. ##### Gauss have I loved

   >其实真没有讲的必要，肯定都会写，输出$n+1>>1$就行了。

2. ##### 抗击疫情

   这道题因为数据给小了，所以暴力能卡过。如果不会写$O(1)$算法的话，也可以写二分。

   ```cpp
   //二分代码
   #include <cstdio>
   int main(){
   	int n,a,b;scanf("%d",&n);
   	while(n--){
   		scanf("%d%d",&a,&b);
           int l=1,r=1500;//r最小为1250(想一想为什么)
   		while(l<=r){
               int mid=l+r>>1;
               if((int)(mid*0.08)>=a&&(int)(mid*0.1)>=b) r=mid-1;else l=mid+1;
            }
   		if((int)(l*0.08)==a&&(int)(l*0.1)==b) printf("%d\n",l);else printf("-1\n");
   	}
   	return 0;
   }
   ```

   ~~其实写二分没必要，毕竟数据太水了，n大约在700000的样子~~

   原型是$Atcoder$上的某一道题，经过各种狂改+玄学操作就变成现在这道题了，原题更水。

3. ##### 安排病房

   就是找规律，也没必要讲。

4. ##### 牌神

   如果实在不会写DP的话，可以拿搜索试试 ~~(显然过不了)~~ 。

   因为没有合适的方法解决本题，且$1 \le N \le 400$，所以可以尝试用区间DP做。

   设$F[i][j]​$表示以第$i​$张牌到第$j​$张牌为一个序列时的最小分数，

   显然有$F[i][j]=min(F[i][j],F[i][k]+w[i]*w[k]*w[j]+F[k][j])$ 。

   因为不包括第$i$张牌和第$j$张牌，所以$F[i][i-1]=F[i][i]=F[i][i+1]=0$ 。

   代码：

   ```cpp
   #include <cstdio>
   #include <cstring>
   #define min(a,b) (a)<(b)?(a):(b)
   int f[402][402],w[402],n;
   int main(){
   	scanf("%d",&n);for(int i=1;i<=n;i++) scanf("%d",&w[i]);
       memset(f,0x3f,sizeof f);
   	for(int i=1;i<=n;i++) f[i][i-1]=f[i][i]=f[i][i+1]=0;
       for(int i=2;i<n;i++) f[i-1][i+1]=w[i-1]*w[i]*w[i+1];//这个不用解释了吧
   	for(int i=n-2;i>=1;i--)//枚举左端点
           for(int j=i+2;j<=n;j++)//枚举右端点
               for(int k=i+1;k<j;k++)//枚举断点
                   f[i][j]=min(f[i][j],f[i][k]+w[i]*w[k]*w[j]+f[k][j]);
       printf("%d\n",f[1][n]);
   	return 0;
   }
   ```

### 第二场比赛：

1. 同第一场比赛第二题

2. 同第一场比赛第四题

3. ##### 双重培优

   根据数据范围只能用DP。

   设$F[i][j]$表示前$i$个人做$j$本艰难培优时所需要的最少的IQ值，$s[i]$表示从$1$到$i$的艰难培优的本数。

   转移方程：$F[i][j]=min(F[i-1][x]+(s[j]-s[x])*[j-x-(s[j]-s[x])],F[i][j])$

   即到第$i$个人做$j$本培优的最少IQ值等于前$i-1$个人做$k$本培优的最少IQ值加上$(j-k)$本培优之间的冲突值。

   ```cpp
   #include <cstdio>
   #include <cstring>
   int f[503][503],a[503],n,k,ans;
   int main(){
   	scanf("%d%d",&n,&k);memset(f,0x3f,sizeof f);f[0][0]=0;
       for(int i=1;i<=n;i++) scanf("%d",&a[i]),a[i]+=a[i-1];//a[i]是前缀和
   	for(int i=1;i<=k;i++)
           for(int j=1;j<=n;j++)
               for(int l=0;l<j;l++)
                   f[i][j]=min(f[i][j],f[i-1][l]+(a[j]-a[l])*(j-l-a[j]+a[l])); 
       printf("%d\n",f[k][n]);
   	return 0;
   }
   ```

4. 最省时的方案

   最短路+计数，用$ans[i]$表示$S$市到$i$市的最省时的方案数，把路径的权值看作1就行了。

   如果$dis[y]=dis[x]+1$的话，说明有$(ans[y]+ans[x])$种方案，$ans[y]$应加上$ans[x]$；

   如果$dis[y]>dis[x]+1$的话，说明$ans[x]$比$ans[y]$优，$ans[y]$应等于$ans[x]$。

   初始化：$ans[S]=1$。

   其实不用考虑自环和重边的。

   ```cpp
   #include <cstdio>
   #include <queue>
   #include <cstring>
   struct Edge{
       int to,next;
   }e[2000002];
   int n,m,len,head[1000002],dis[1000002],ans[1000002],s;
   std::queue<int> q;
   bool vis[1000002];
   void addedge(int &u,int &v){
       e[++len].next=head[u];
       head[u]=len;
       e[len].to=v;
   }
   int main(){
       scanf("%d%d%d",&n,&m,&s);
       for(int i=1;i<=m;i++){
           int u,v;scanf("%d%d",&u,&v);
           addedge(u,v),addedge(v,u);//无向图
       }
       //SPFA:
       memset(dis,0x3f,sizeof dis),dis[s]=0;
       vis[s]=1,ans[s]=1,q.push(s);
       while(!q.empty()){
           int x=q.front();q.pop();
           vis[x]=0;
           for(int i=head[x];i;i=e[i].next){
               if(dis[e[i].to]>dis[x]+1){
                   dis[e[i].to]=dis[x]+1;
                   ans[e[i].to]=ans[x];
                   if(!vis[e[i].to]) vis[e[i].to]=1,q.push(e[i].to);
               }
               else{
                  if(dis[e[i].to]==dis[x]+1)
                      ans[e[i].to]=(ans[e[i].to]+ans[x])%2580000;
               }
           }
       }
       for(int i=1;i<=n;i++) printf("%d\n",ans[i]);
       return 0;
   }
   ```

   ~~对了：关于SPFA，它死了~~

   也许写$Dijkstra$会快一点，但数据中$M$没有那么大，两个都可以。