20191017测试总结
T1:WOJ4756
送分题,记得开long long)雾
#include <iostream>
#include <cstdio>
using namespace std;
int n, m, s, t, a, w, d[200005];
long long ans;
int read()
{
int x = 0;
char c = getchar();
while (!isdigit(c))
c = getchar();
while (isdigit(c))
{
x = (x << 3) + (x << 1) + (c ^ 48);
c = getchar();
}
return x;
}
int main()
{
n = read();
m = read();
for (int i = 2; i <= m; ++i)
{
a = read();
d[i] = d[i - 1] + a;
}
for (int i = 1; i <= n; ++i)
{
s = read();
t = read();
w = read();
ans += (d[t] - d[s]) * w;
}
printf("%lld", ans);
return 0;
}
T2:WOJ4757
挺有意思的一道DP,不过推出来了转移状态之后就不知道该干什么了。
原来DP的转移可以通过转换为下标来优化复杂度,以后数据范围小的题如果想不出来都应该想想这个方法。
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
int n, num, s = 1, c[100005], f[100005];
struct node
{
int id;
int a;
} a[100005];
inline int read()
{
int x = 0;
char c = getchar();
while (!isdigit(c))
c = getchar();
while (isdigit(c))
{
x = (x << 3) + (x << 1) + (c ^ 48);
c = getchar();
}
return x;
}
bool cmp(node aa, node bb)
{
return aa.a < bb.a;
}
int lowbit(int x)
{
return x & -x;
}
void add(int x, int val)
{
while (x <= n)
{
c[x] = max(c[x], val);
x += lowbit(x);
}
return;
}
int query(int x)
{
int ans = 0;
while (x >= 1)
{
ans = max(ans, c[x]);
x -= lowbit(x);
}
return ans;
}
int main()
{
n = read();
for (register int i = 1; i <= n; ++i)
{
a[i].id = i;
a[i].a = read();
}
sort(a + 1, a + n + 1, cmp);
for (int i = 1; i <= n; ++i)
{
if (a[i].id >= a[i].a)
f[i] = query(a[i].id - a[i].a + 1) + 1;
if (a[i].a != a[i + 1].a)
{
for (int j = s; j <= i; ++j)
if (a[j].id >= a[j].a)
add(a[j].id - a[j].a + 1, f[j]);
s = i + 1;
}
num = max(num, f[i]);
}
printf("%d", num);
return 0;
}
T3:WOJ4758
又是一道成功想出来了离正解差一点点的方法的题目。。。
通过x,y坐标分别排序之后就可以从前到后连边来解决问题了,极大的减少了边的数量。
看来我还需要多练习一下图论的建图题啊。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std;
int n, sum, vis[200005], d[200005], head[200005];
struct node
{
int v;
int w;
int next;
} a[800005];
struct bili
{
int id;
int x;
int y;
} b[200005];
struct point
{
int id;
int d;
point(int aa, int bb)
{
id = aa;
d = bb;
}
bool operator<(point bb) const
{
return d > bb.d;
}
};
priority_queue<point> q;
inline int read()
{
int x = 0;
char c = getchar();
while (!isdigit(c))
c = getchar();
while (isdigit(c))
{
x = (x << 3) + (x << 1) + (c ^ 48);
c = getchar();
}
return x;
}
void ins(int u, int v, int w)
{
++sum;
a[sum].v = v;
a[sum].w = w;
a[sum].next = head[u];
head[u] = sum;
return;
}
bool cmp1(bili aa, bili bb)
{
return aa.x < bb.x;
}
bool cmp2(bili aa, bili bb)
{
return aa.y < bb.y;
}
void dijkstra()
{
memset(d, 0x7f, sizeof(d));
d[1] = 0;
q.push(point(1, 0));
while (!q.empty())
{
point k = q.top();
q.pop();
if (vis[k.id])
continue;
vis[k.id] = 1;
if (k.id == n)
break;
int dd = head[k.id];
while (dd)
{
if (!vis[a[dd].v] && d[a[dd].v] > d[k.id] + a[dd].w)
{
d[a[dd].v] = d[k.id] + a[dd].w;
q.push(point(a[dd].v, d[a[dd].v]));
}
dd = a[dd].next;
}
}
return;
}
int main()
{
n = read();
for (int i = 1; i <= n; ++i)
{
b[i].id = i;
b[i].x = read();
b[i].y = read();
}
sort(b + 1, b + n + 1, cmp1);
for (int i = 1; i < n; ++i)
{
ins(b[i].id, b[i + 1].id, b[i + 1].x - b[i].x);
ins(b[i + 1].id, b[i].id, b[i + 1].x - b[i].x);
}
sort(b + 1, b + n + 1, cmp2);
for (int i = 1; i < n; ++i)
{
ins(b[i].id, b[i + 1].id, b[i + 1].y - b[i].y);
ins(b[i + 1].id, b[i].id, b[i + 1].y - b[i].y);
}
dijkstra();
printf("%d", d[n]);
return 0;
}
评论
发表评论