这次又是课后订正。。。。

我好菜啊QAQ，只做了400分

T1：

一道简单的方程题

设x=A-a，即利润

可得A-a+B-b-x=C-a-b

移项后得A+B-C=x

code:

#include<bits/stdc++.h>
using namespace std;
int T,a,b,c;
int main(){
    scanf("%d",&T);
    while(T--){
        scanf("%d%d%d",&a,&b,&c);
        printf("%d\n",a+b-c);
    }
    return 0;
}

T2:

大模拟，首先计算出上下两面的表面积贡献为2nm

然后考虑左右前后四面，每一个凸出来的方块肯定会被计算一次表面积

于是枚举四个方向，加入答案即可

code:

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int h,w,a[110][110];
ll ans;
int main(){
    scanf("%d%d",&h,&w);
    for(int i=1;i<=h;i++)
        for(int j=1;j<=w;j++)
            scanf("%d",&a[i][j]);
    ans=h*w*2;
    for(int i=1;i<=h;i++)
        for(int j=1;j<=w;j++){
            if(a[i-1][j]<a[i][j]) ans+=a[i][j]-a[i-1][j];
            if(a[i+1][j]<a[i][j]) ans+=a[i][j]-a[i+1][j];
            if(a[i][j-1]<a[i][j]) ans+=a[i][j]-a[i][j-1];
            if(a[i][j+1]<a[i][j]) ans+=a[i][j]-a[i][j+1];
        }
    printf("%lld",ans);
    return 0;
}

T3：

首先考虑最短路，在无权图上的最短路肯定是BFS跑的最快啦（摘自PPT）

然后考虑计算路径，可以记录一个最短路的前缀，也就是从哪里来的，然后最后倒着回去输出即可

code:

#include<bits/stdc++.h>
#define pii pair<int,int> 
#define ll long long
#define fi first
#define se second
#define mk make_pair
using namespace std;
int n,sx,sy,ex,ey;
int h,t;
int nxt[6][2]={-2,-1,-2,1,0,2,2,1,2,-1,0,-2};
char name[6][10]={"UL","UR","R","LR","LL","L"};
int ans[500010],cnt;
int vis[210][210];
struct node{
    int x,y,las;
    int ans;
}q[500010];
bool check(int x,int y){return (!vis[x][y])&&(x>=0)&&(x<n)&&(y>=0)&&(y<n);}
int main(){
    scanf("%d%d%d%d%d",&n,&sx,&sy,&ex,&ey);
    q[++t]=(node){sx,sy,0,-1};
    vis[sx][sy]=1;
    while(h<t){
        pii now;
        now.fi=q[++h].x;
        now.se=q[h].y;
        for(int i=0;i<6;i++){
            int nx=now.fi+nxt[i][0];
            int ny=now.se+nxt[i][1];
            if(!check(nx,ny)) continue;
            vis[nx][ny]=1; 
            q[++t].las=h;
            q[t].ans=i;
            q[t].x=nx;
            q[t].y=ny;
            if(nx==ex&&ny==ey){
                while(q[t].las!=0){
                    ans[++cnt]=q[t].ans;
                    t=q[t].las;
                }
                printf("%d\n",cnt);
                while(cnt>0){printf("%s ",name[ans[cnt]]);cnt--;}
                return 0;
            }
        }
    }
    puts("Impossible");
    return 0;
}

T4:

一道显然的数学题（其实也可以用DP来做）

首先想到的就是DP，设：

f[i][0]表示第i个点放1的方案数

f[i][1]表示第i个点放x的方案数

f[i][2]表示第i个点既不放1也不放x的方案数

然后可以得到DP方程：

f[i][0]=f[i-1][1]+f[i-1][2]

f[i][1]=f[i-1][0]+f[i-1][2]

f[i][2]=f[i-1][2](k-3)+f[i-1][0](k-2)+f[i-1][1]*(k-2)

初始化f[1][0]=1。

但是有一种特殊情况，那就是x==1.这时候可以把x当做1来做，直接输出f[n-2][0](k-1)+f[n-2][2](k-1)

code:

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll f[100010][3],n,k,x;
const ll mod=1e9+7;
int main(){
    scanf("%d%d%d",&n,&k,&x);
    f[1][0]=1;
    for(int i=2;i<n;i++){
        f[i][0]=(f[i-1][1]+f[i-1][2])%mod;
        f[i][1]=(f[i-1][0]+f[i-1][2])%mod;
        f[i][2]=(f[i-1][2]*(k-3)%mod+f[i-1][0]*(k-2)%mod+f[i-1][1]*(k-2)%mod)%mod;
    }
    if(x==1) printf("%lld",(f[n-2][0]+f[n-2][2])*(k-1)%mod); 
    else printf("%lld",(f[n-1][0]+f[n-1][2])%mod);
    return 0;
}