暑期cspj模拟赛2

第三期的题目 https://www.luogu.com.cn/contest/65483#problems

T1

#include<bits/stdc++.h>
using namespace std;
int a[100005];
bool flag = 0;

int main() {
    int m;
    cin >> m;
    cin >> a[1];
    for (int i = 2; i <= m; i++) {
        cin >> a[i];
        if (a[i] != a[i - 1])flag = 1;
    }
    if (!flag)cout << 0;
    else cout << m - 1;
    return 0;
}

T2

#include<bits/stdc++.h>//万能头文件，美丽又大方
using namespace std;
int n,t,w[100001][2];//分别表示蚂蚁数量，时间长度，以及t秒后按位置从大到小排名后的位置及方向
struct node{//结构体方便排序
	int w,f,h,d;
}ant[100001];//记录信息，分别为每只蚂蚁的位置，方向，输入序号以及位置永久排名（位置排名不变）
int cmp(node x,node y){//排序方式1：按照位置排序
	return x.w<y.w;
}
int cmp1(node x,node y){//排序方式2：按照输入序号排序
	return x.h<y.h;
}
int main(){
    scanf("%d%d",&n,&t);
    for (int i=1;i<=n;i++){
    	scanf("%d%d",&ant[i].w,&ant[i].f);
    	ant[i].h=i;
	}//简单输入以及标号
	sort(ant+1,ant+1+n,cmp);//按照t秒前的位置排序
	for (int i=1;i<=n;i++){
		ant[i].d=i;//定位永久位置排名
    	ant[i].w+=ant[i].f*t;//模拟每个蚂蚁t秒后的位置
	}
	sort(ant+1,ant+1+n,cmp);//按照t秒后的位置排序
	for (int i=2;i<=n;i++){//判断是否正在转弯（如相邻两蚂蚁坐标相等，即为正在转弯）
		if (ant[i].w==ant[i-1].w){
			ant[i].f=0;ant[i-1].f=0;//标记输出时的状态
		}
	}
	for (int i=1;i<=n;i++){//填充记录从小到大蚂蚁的位置及方向
		w[i][0]=ant[i].w;
		w[i][1]=ant[i].f;
	}
	sort(ant+1,ant+1+n,cmp1);//按照输入序号排序
	for (int i=1;i<=n;i++){//按照输入时的顺序依次按照各自的永久位置输出每一只蚂蚁的坐标及状态
		printf("%d %d\n",w[ant[i].d][0],w[ant[i].d][1]);
	}
    return 0;//好习惯，人人养成
}

T3

#include<bits/stdc++.h>
using namespace std;

int c[200005];
long long s[200005]; // 前缀和

int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);

    int t;
    std::cin >> t;
    while (t--)
    {
        int n, x, y;
        long long ans1 = 0, ans2 = 0, ans3 = 0;

        s[1] = 0; // 前缀和注意初始化

        std::cin >> n;
        for (int i = 1; i <= n; i++)
        {
            int r;
            std::cin >> r;
        }
        for (int i = 1; i <= n; i++)
        {
            std::cin >> c[i];
            s[i] = s[i - 1] + c[i];
        }

        x = n + 1, y = 0;            // 初始化，防止找不到
        for (int i = 1; i <= n; i++) // 寻找 x
            if (c[i] <= 0)
            {
                x = i;
                break;
            }
        for (int i = n; i >= 1; i--) // 寻找 y
            if (c[i] >= 0)
            {
                y = i;
                break;
            }

        // 计算答案
        for (int i = 1; i < x - 1; i++)
            ans1 = std::max(ans1, s[x - 1] - s[i] - c[i]);
        for (int i = n; i > y + 1; i--)
            ans3 = std::max(ans3, 0 - (s[i - 1] - s[y]) + c[i]);
        for (int i = x; i <= y; i++)
            ans2 += abs(c[i]);

        std::cout << ans1 + ans2 + ans3 << "\n";
    }

    return 0;
}

T4

#include<bits/stdc++.h>

using namespace std;

struct node {
    long long x, y, dis;

    bool operator <(const node& b) const {
        return dis > b.dis;
    }
};

long long num[1001][1001], dis[3][1001][1001];
int n, m, a, b, c, dx[4] = {-1, 1, 0, 0}, dy[4] = {0, 0, -1, 1};

void dijkstra(int k, int sx, int sy) {
    priority_queue<node> q;
    q.push((node){sx, sy, num[sx][sy]});
    bool vis[1001][1001] = {0};
    for (int i = 1; i <= 1000; i++) {
        for (int j = 1; j <= 1000; j++) {
            dis[k][i][j] = 1e18;
        }
    }
    dis[k][sx][sy] = num[sx][sy];
    while (!q.empty()) {
        int x = q.top().x, y = q.top().y;
        q.pop();
        if (vis[x][y]) {
            continue;
        }
        vis[x][y] = 1;
        for (int i = 0; i < 4; i++) {
            int tx = x + dx[i], ty = y + dy[i];
            if (tx < 1 || tx > n || ty < 1 || ty > m) {
                continue;
            }
            if (dis[k][tx][ty] > dis[k][x][y] + num[tx][ty]) {
                dis[k][tx][ty] = dis[k][x][y] + num[tx][ty];
                q.push((node){tx, ty, dis[k][tx][ty]});
            }
        }
    }
}

int main() {
    scanf("%d%d%d%d%d", &n, &m, &a, &b, &c);
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            scanf("%lld", &num[i][j]);
        }
    }
    dijkstra(0, 1, a);
    dijkstra(1, n, b);
    dijkstra(2, n, c);
    long long ans = 1e18;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            ans = min(ans, dis[0][i][j] + dis[1][i][j] + dis[2][i][j] - 2 * num[i][j]); //注意这里交叉点的部分会多算两次，所以要减掉
        }
    }
    printf("%lld", ans);
    return 0;
}