Problem 2167 大王叫我来巡山呐

做的的第二题 呵呵

Problem 2168 防守阵地 I

做的第一题

打了下草稿 马上切了它

假设当前x=(ai)*1+(ai+1)*2+(ai+2)*3+‘‘‘‘+(aj)*m

下一次是(ai+1)*1+(ai+2)*2+(ai+3)*3+‘‘‘‘+(aj+1)*m = (ai)*1+(ai+1)*2+(ai+2)*3+‘‘‘‘+(aj)*m+(aj+1)*(m+1) -(ai+(ai+1)+(ai+2)+‘‘‘+(aj)+(aj+1))

紫色的这一段是连续的 直接前缀和预处理

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 1000010;
int n, m;
int a[maxn];
int b[maxn];
int main()
{
	while(scanf("%d %d", &n, &m) != EOF)
	{
		__int64 ans = 0;
		for(int i = 1; i <= n; i++)
		{
			scanf("%d", &a[i]);
			b[i] = b[i-1] + a[i];
			if(i <= m)
				ans += i*a[i];
		}
		__int64 x = ans;
		for(int i = m+1; i <= n; i++)
		{
			
			__int64 temp = x + (m+1) * a[i];
			temp -= b[i] - b[i-m-1];
			x = temp;
			ans = max(ans, temp);
		}
		printf("%I64d\n", ans);
	}
	return 0;
}

Problem 2169 shadow

做的第三题

开始想直接广搜了 不过被消灭的军队是不能在被消灭一次的 开始不知道怎么处理 后来想了下

如果某些军队经过最短路的上的点是同一点 那么接下来他们走的路应该是一样的 所以直接contine

另外开了个数组sum sum[u]代表到u这个点为止 包括之前的消灭的军队总数
 

#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
using namespace std;
const int maxn = 100010;
int d[maxn];
int sum[maxn];
int a[maxn];
int b[maxn];
int vis[maxn];
vector <int> G[maxn];
int n, m;

void BFS()
{
	queue <int> Q;
	for(int i = 0; i <= n; i++)
		d[i] = 999999999;
	memset(sum, 0, sizeof(sum));
	for(int i = 1; i <= m; i++)
	{
		Q.push(b[i]);
		d[b[i]] = 0;
		vis[b[i]] = 1;
	}
	while(!Q.empty())
	{
		int u = Q.front(); Q.pop();
		for(int i = 0; i < G[u].size(); i++)
		{
			int v = G[u][i];
			
			if(vis[v])
			{
				sum[v] += sum[u];
				sum[u] = 0;
				continue;
			}
			vis[v] = true;
			if(d[v] > d[u] + 1)
			{
				sum[v] += sum[u] + a[v];
				sum[u] = 0;
				d[v] = d[u] + 1;
				Q.push(v);
			}
		}		
	}
}
int main()
{
	while(scanf("%d %d", &n, &m) != EOF)
	{
		for(int i = 0; i <= n; i++)
		{
			G[i].clear();
		}
		for(int i = 1; i <= n; i++)
		{
			scanf("%d", &a[i]);
		}
		for(int i = 1; i <= m; i++)
		{
			scanf("%d", &b[i]);
		}
		for(int i = 1; i < n; i++)
		{
			int u, v;
			scanf("%d %d", &u, &v);
			G[u].push_back(v);
			G[v].push_back(u);
		}
		memset(vis, 0, sizeof(vis));
		BFS();
		int ans = 0;
		for(int i = 1; i <= n; i++)
			ans += sum[i];
		printf("%d\n", ans);
	}
	return 0;
}

Problem 2170 花生的序列

由于聊聊天 看看动漫没时间了 本来想看这题的 有空再想想

Problem 2171 防守阵地 II

做的第四题

看了下题目 尼玛线段树成段更新！！！！ 直接线段树搞过去 代码太恶心 不过真的是水题啊

#include <stdio.h>
#define MAX 100010
struct node
{
	int l;
	int r;
	int sum;
	int add;
}a[MAX*4];

void build(int l,int r,int rt)
{
	a[rt].l = l;
	a[rt].r = r;
	a[rt].add = 0;
	if(l == r)
	{
		scanf("%d", &a[rt].sum);
		return;
	}
	int m = (l + r) >> 1;
	build(l,m,rt<<1);
	build(m+1,r,rt<<1|1);
	a[rt].sum = a[rt<<1].sum + a[rt<<1|1].sum;
}

void update(int l,int r,int rt,int add)
{
	if(a[rt].l == l && a[rt].r == r)
	{
		a[rt].add += add;
		a[rt].sum += add * (r-l+1);
		return;
	}
	if(a[rt].l == a[rt].r)
		return;
	if(a[rt].add)
	{
		int k = a[rt].r - a[rt].l + 1;
		a[rt<<1].add += a[rt].add;
		a[rt<<1|1].add += a[rt].add;
		a[rt<<1].sum += a[rt].add*(k - (k>>1));
		a[rt<<1|1].sum += a[rt].add*(k>>1);
		a[rt].add = 0;
	}
	int m = (a[rt].l + a[rt].r) >> 1;
	if(r <= m)
		update(l,r,rt<<1,add);
	else if(l > m)
		update(l,r,rt<<1|1,add);
	else
	{
		update(l,m,rt<<1,add);
		update(m+1,r,rt<<1|1,add);
	}
	a[rt].sum = a[rt<<1].sum + a[rt<<1|1].sum;
}
int query(int l, int r, int rt)
{
	if(a[rt].l == l && a[rt].r == r)
	{
		return a[rt].sum;
	}
	if(a[rt].l == a[rt].r)
		return 0;
	
	if(a[rt].add)
	{
		int k = a[rt].r - a[rt].l + 1;
		a[rt<<1].add += a[rt].add;
		a[rt<<1|1].add += a[rt].add;
		a[rt<<1].sum += a[rt].add*(k - (k>>1));
		a[rt<<1|1].sum += a[rt].add*(k>>1);
		a[rt].add = 0;
	}
	int m = (a[rt].l + a[rt].r) >> 1;
	int res = 0;
	if(r <= m)
		res = query(l,r,rt<<1);
	else if(l > m)
		res = query(l,r,rt<<1|1);
	else
	{
		res += query(l,m,rt<<1);
		res += query(m+1,r,rt<<1|1);
	}
	a[rt].sum = a[rt<<1].sum + a[rt<<1|1].sum;
	return res;
}
	
int main()
{
	int n, m, q;
	while(scanf("%d %d %d",&n, &m, &q) != EOF)
	{		
		build(1, n, 1);
		while(q--)
		{
			int x;
			scanf("%d", &x);
			printf("%d\n", query(x, x+m-1, 1));
			update(x, x+m-1, 1, -1);
		}
	}	
	return 0;
}

Problem 2172 巡了南山我巡北山

没看呢

Problem 2173 Nostop

做的第五题

第一感觉是floyd+矩阵快速幂 10亿次floyd肯定不行嘛 矩阵快速幂加速啊

要多做做经典题目啊！！！POJ 3613 这种经典题目很多啊 我们要学经典题目 然后举一反三

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const __int64 fd = 1;
const __int64 INF = fd<<55;
const int maxn = 55;
struct Mat
{
    __int64 a[maxn][maxn];
};
Mat A, B, C, D;
int n, m;

Mat floyd(Mat x, Mat y)
{
	Mat z;
	for(int i = 1; i <= n; i++)
		for(int j = 1; j <= n; j++)
		{
			z.a[i][j] = INF;
			
		}
	for(int k = 1; k <= n; k++)
		for(int i = 1; i <= n; i++)
			for(int j = 1; j <= n; j++)
		 		z.a[i][j] = min(z.a[i][j], x.a[i][k] + y.a[k][j]);
	return z;
}
/*Mat get(Mat x, Mat y)
{
    Mat z;
    memset(z.a, 0, sizeof(z.a));
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++)
            for(int k = 1; k <= n; k++)
            {
                z.a[i][j] += x.a[i][k]*y.a[k][j];
                //z.a[i][j] %= mod;
            }
    return z;
}*/
void Mat_pow(int x)
{
    while(x)
    {
        if(x&1)
            B = floyd(B, A);
        A = floyd(A, A);
        x >>= 1;
    }
}
int main()
{
	int T;
	scanf("%d", &T);
	while(T--)
	{
		int x;
		scanf("%d %d %d", &n, &m, &x);

		for(int i = 1; i <= n; i++)
			for(int j = 1; j <= n; j++)
			{
				A.a[i][j] = B.a[i][j] = INF;
				if(i == j)
					B.a[i][j] = 0;
			}
		while(m--)
		{
			int u, v;
			__int64 w;
			scanf("%d %d %I64d", &u, &v, &w);
			if(A.a[u][v] > w)
				A.a[u][v] = w;
		}
		Mat_pow(x);
		if(B.a[1][n] == INF)
			puts("-1");
		else
			printf("%I64d\n", B.a[1][n]);
	}
	return 0;
}

Problem 2174 卷福的难题

没看呢

最后总结一下 前面4题都1A的 最后一题忘记处理-1的情况 坑！！！

不过还是得更加努力 某一方面研究的更深