A. Dead Pixel（思路）
思路
题意：给我们一个m*n的表格，又给了我们表格中的一个点a，其坐标为(x, y),问在这个表格中选择一个不包括改点a的最大面积的矩形，输出这个最大面积
分析：很明显这个点 可以将 m*n的表格分成四份，而每一份又可以分成 举行的长或宽不被点a影响的两小份，接下来就是比较讨论了
代码
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<map>
#include<string>
#include<vector>
#include<queue>
#include<stack>
using namespace std;
#define Max(a, b, c, d) max(max(a, b), max(c, d))
int m,n,x,y;
int Area(int x1, int y1, int x2, int y2)
{
int s1 = abs(x1 - x2) * n;
int s2 = abs(y1 - y2) * m;
return max(s1, s2);
}
int main()
{
/* freopen("A.txt","r",stdin); */
/* freopen("Ans.txt","w",stdout); */
int t;
scanf("%d", &t);
while(t --)
{
scanf("%d %d %d %d", &m, &n, &x, &y);
x ++, y ++;
int a = Area(1, 1, x, y);
int b = Area(1, n, x, y);
int c = Area(m, 1, x, y);
int d = Area(m, n, x, y);
printf("%d\n", Max(a, b, c, d));
}
return 0;
}
B. Homecoming（思路）
思路
分析：从后往前计算路费，把所给的字符串的最后一个字符设置成 非‘A’、‘B’的字符，从倒数第二个字符开始，与前一个字符相同则 则与之前的钱数相同，否则 在之前前的基础上加上 原来的 当前讨论的字符所需的钱数
代码
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<map>
#include<string>
#include<vector>
#include<queue>
#include<stack>
using namespace std;
#define Max(a, b, c, d) max(max(a, b), max(c, d))
#define ll long long
const int Len = 1e6;
int a, b, p;
char s[Len];
ll mon[Len];
int main()
{
/* freopen("A.txt","r",stdin); */
/* freopen("Ans.txt","w",stdout); */
int t;
scanf("%d", &t);
while(t --)
{
scanf("%d %d %d", &a, &b, &p);
scanf("%s", s + 1);
int n = strlen(s + 1);
mon[n] = 0;
s[n] = 'C';
for(int i = n - 1; i >= 1; i --)
{
mon[i] = mon[i + 1];
if(s[i] != s[i + 1])
{
if(s[i] == 'A')
mon[i] += a;
else
mon[i] += b;
}
/* printf("mon[%d] = %d\n", i, mon[i]); */
}
for(int i = 1; i <= n; i ++)
{
if(p >= mon[i])
{
printf("%d\n", i);
break;
}
}
}
return 0;
}
C. Restoring Permutation（思路）
思路
题意：给我们一个长度为2n的ar数组（由1～2n之间的数组成） 和一个长度为n的br数组，在br数组中的元素（由1～2n之间的数组成）: \(br[ i ] = min(ar[2*i - 1], ar[2*i])\), 现在给我们了 br的n个元素，求出 是否一个能找出来一个满足定义br时要求序列ar，如果有输出那个字典序最小的那个，否则输出-1.
分析：对于任意一对\(ar[2*i - ]，ar[2*i] ~~ (1=<i<= n)\),首先我们一定知道它们两个中最小的那个是br[i], 但是题目要求我们字典序最小，这时候如果有符合题意的数组ar的话，那么肯定是\(ar[2*i-1] == br[i]\)(字典序最小的原因)，剩下的就是根据贪心的思想，但我们从左到右 依次讨论\(ar[2*1],ar[2*2],ar[2*3],,,ar[2*n]\) 这些空位的值我们应该怎么填了，首先填这些空的数字必须是 1~2*n 中没有在br中出现过的数字，但我们在遍历讨论要填某个空 \(ar[2*i]\)的值时，首先要求是\(ar[2*i] > ar[2*i-1]\),这样符合定义 \(br\) 时的要求，其次是：\(ar[2*i]\)要尽可能的靠近\(ar[2*i-1]\),这样我们根据这个思路去循环的填写每一个空\(ar[2*i]\),就能得到答案了
代码
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<map>
#include<string>
#include<vector>
#include<queue>
#include<stack>
using namespace std;
#define Max(a, b, c, d) max(max(a, b), max(c, d))
#define ll long long
const int Len = 1e3;
int n;
int pos[Len];
map<int, int> use;
int ans[Len];
int ar[Len];
int main()
{
/* freopen("A.txt","r",stdin); */
/* freopen("Ans.txt","w",stdout); */
int t;
scanf("%d", &t);
while(t --)
{
memset(ar, 0, sizeof(ar));
scanf("%d", &n);
for(int i = 1; i <= n; i ++)
{
scanf("%d", &ar[i]);
ans[2*i - 1] = ar[i];
ans[2*i] = 0;
use[ar[i]] = 1;
}
for(int i = 1; i <= n; i ++)
{
int last = 1;
while(use[last] > 0 || last <= ar[i])
last ++;
if(last > 2*n) break;
ans[2*i] = last;
use[last] = 1;
}
int flag = 1;
for(int i = 1; i <= 2*n; i ++)
if(! ans[i])
{
flag = 0;
break;
}
if(flag)
{
for(int i = 1; i <= 2*n; i ++)
printf("%d ", ans[i]);
printf("\n");
}
else
printf("-1\n");
use.clear();
}
return 0;
}
D. Recommendations（并查集+贪心）
思路
题意：给我一个n个元素的序列：\(ar\), 我可以增加这个序列中的某些元素的值，但是我们我们每将ar序列中的某个元素值+1，会耗费一定代价，又给我们一个耗费代价的序列 \(br\) , 其中\(br[i]\) 把ar中的第i个元素+1的耗费代价，问我把序列ar中的元素通过 “加数操作” 边的各不相同，需要耗费的最小代价是多少？？（注意：只能在原来原来的元素上添加值）
分析：这一题自己做的时候很懵逼，完全没有思路，后来baidu了一下看都是用并查集写的，真是考思维啊， 现在理解的可能也不太好，首先就是 把自定义的结构体数组中的元素 首先按增加某个值代价，按从大到小排序，如果代价相同 就按ar中的数从 小到大 来拍序，首先我我想先说一个规律：对于一个ar序列如：1 3 3 4，我们想不考虑它们增加值的代价是多少，对于第一种变换方法：我们可以把 改变其中一个3->4，在改变原来的那个4改变为 4 -> 5, 这样得到的序列是 ：1 3 4 5，另一种该法就是直接把 3->4，在把这个4（是由3变换过来的）变为 4->5 这样得到的序列也是 ：1 3 4 5 ; 通过这样的两种变化方式，可以发现它们的 +1 的过程都经过了两次，通过这样我们的总结：对于任意一个序列 我们要想把它的各个元素变的不一样，我们所需要的最小的变化次数（即： +1 的次数）是相同的。。。这样我们无论怎么操作+1最小次数不变，那么而我们 +1是需要的费用是不同的，那么对于某个序列的任意一次+1 操作我们要尽量选择 代价小的那个数进行+1，而我们排序的规则正好符合这个要求，而并查集的真实维护的过程大概是： 对于第一出现的元素x，花费+0，然后在让x的父节点fx与fx+1，合并到一个集合中去，其中只能是 fx+1 为父节点，对于重复出现的元素，并查集已经找到了最少要变化得到的值，那直接计算这个变化的到这个值的花费是多少就行了，然后在建立节点关系，在讨论下一个元素。。。。。
代码
#include<iostream>
#include<algorithm>
#include<map>
using namespace std;
#define ll long long
const int Len = 300000;
map<int, int> fa;
struct Node
{
int data, cost;
bool operator < (const Node b) const
{
if(cost == b.cost)
return data < b.data;
return cost > b.cost;
}
} node[Len];
int find(int x)
{
if(fa[x] == 0) return x;
return fa[x] = find(fa[x]);
}
void Union(int x, int y)
{
int fx = find(x);
int fy = find(y);
if(fx != fy)
fa[fx] = fy;
}
int main()
{
/* freopen("A.txt","r",stdin); */
fa.clear();
int n;
scanf("%d", &n);
for(int i = 1; i <= n; i ++)
scanf("%d", &node[i].data);
for(int i = 1; i <= n; i ++)
scanf("%d", &node[i].cost);
sort(node + 1, node + 1 + n);
ll ans = 0;
for(int i = 1; i <= n; i ++)
{
int fx = find(node[i].data);
ans += node[i].cost * 1LL * (fx - node[i].data);
Union(fx, fx + 1);
}
printf("%lld", ans);
return 0;
}
