好几天了，一定要进校队！
7.21场地址
A题：
题意：类比竖式加法，每个字母都要分配一个数字，最后一行是结果，之前多行是因数，求一共存在多少种字母的分配方案
解法：枚举每一个字母，每枚举一个检查一遍
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <vector>
#include <math.h>
#include <bitset>
#include <algorithm>
#include <climits>
using namespace std;
#define ls 2*i
#define rs 2*i+1
#define UP(i,x,y) for(i=x;i<=y;i++)
#define DOWN(i,x,y) for(i=x;i>=y;i--)
#define MEM(a,x) memset(a,x,sizeof(a))
#define W(a) while(a)
#define gcd(a,b) __gcd(a,b)
#define LL long long
#define N 20005
#define INF 0x3f3f3f3f
#define EXP 1e-8
#define rank rank1
const int mod = 1000000007;
int n, letter[20], cot, len[20], hsh[200], num[200], ans;
char str[20][20];
int check(){
int i, j, k;
for (i = 0; i<n; i++)//前导0不行
{
if (num[str[i][0]] == 0)
return 0;
}
int jin = 0;//进位
for (j = 0; j<len[n - 1]; j++)//从右边（个位）开始算
{
if (num[str[n - 1][len[n - 1] - 1 - j]] == -1) return 1;//这个字母没有被赋值，返回并往下搜
int sum = jin;
for (i = 0; i<n - 1; i++){
if (len[i] - 1 - j<0) continue;
if (num[str[i][len[i] - 1 - j]] == -1) return 1;//这个字母没有被赋值，返回并往下搜
sum += num[str[i][len[i] - 1 - j]];
}
if (sum % 10 != num[str[n - 1][len[n - 1] - 1 - j]]) return 0;//对应位之和与最后一个不等
jin = sum / 10;
}
return !jin;//进位为0则解决了
}
void dfs(int cnt)
{
int i;
if (cnt == -1)
{
ans++;
return;
}
for (i = 0; i<10; i++)//给字母尝试所有不同的赋值赋值
{
if (hsh[i] == 0)
{
hsh[i] = 1;
num[letter[cnt]] = i;
if (check())//赋值可行则继续进行
dfs(cnt - 1);
hsh[i] = 0;
num[letter[cnt]] = -1;
}
}
}
int main()
{
int i, j, k;
while (~scanf("%d", &n))
{
MEM(hsh, 0);
cot = -1;
for (i = 0; i < n; i++)
{
scanf("%s", str[i]);
len[i] = strlen(str[i]);
for (j = 0; j < len[i]; j++)
{
if (!hsh[str[i][j]])
{
hsh[str[i][j]] = 1;
letter[++cot] = str[i][j];//记录所有字母
}
}
}
ans = 0;
MEM(hsh, 0);
MEM(num, -1);
dfs(cot);
printf("%d
", ans);
}
return 0;
}
B题：
题意：给定起点和终点，统计所有最短路的长度和为多少
解法：首先（最短路*条数）的方法是行不通的，检验一条路是不是最短路的方法为：
最短路的起点到这条路的的起点的距离+最短路的终点到这条路终点的距离+这条路的距离=最短路。
从起点和终点跑两边spfa，之后枚举每一条边即可
#include<cstdio>
#include<vector>
#include<queue>
#include<cstring>
using namespace std;
typedef long long ll;
const int maxn = 10005;
const int maxm = 600000;
const int INF = 0x3f3f3f3f;
int n, m;
struct ee {
int to;
int nxt;
int w;
}edge[maxm];
int head[maxn], tot;
void add_edge(int u, int v, int w) {
edge[tot].to = v;
edge[tot].w = w;
edge[tot].nxt = head[u];
head[u] = tot++;
}
int vis1[maxn], vis2[maxn];
int dis1[maxn], dis2[maxn];
void spfa1(int s, int t)
{
for (int i = 0; i < n; ++i) dis1[i] = INF;
memset(vis1, false, sizeof( vis1));
queue<int>q;
q.push(s);
dis1[s] = 0;
vis1[s] = true;
while (!q.empty()) {
int u = q.front(); q.pop();
vis1[u] = false;
for (int i = head[u]; ~i; i = edge[i].nxt) {
int &v = edge[i].to;
int &cost = edge[i].w;
if (dis1[v] > dis1[u] + cost) {
dis1[v] = dis1[u] + cost;
if (!vis1[v]) {
vis1[v] = true;
q.push(v);
}
}
}
}
}
void spfa2(int s, int t)
{
for (int i = 0; i<n; ++i) dis2[i] = INF;
memset(vis2, false, sizeof (vis2));
queue<int> q;
q.push(s);
dis2[s] = 0;
vis2[s] = true;
while (!q.empty()) {
int u = q.front(); q.pop();
vis2[u] = false;
for (int i = head[u]; ~i; i = edge[i].nxt) {
int &v = edge[i].to;
int &cost = edge[i].w;
if (dis2[v] > dis2[u] + cost) {
dis2[v] = dis2[u] + cost;
if (!vis2[v]) {
vis2[v] = true;
q.push(v);
}
}
}
}
}
int main() {
scanf("%d%d", &n, &m);
memset(head, -1, sizeof head);
tot = 0;
for (int i = 1; i <= m; i++) {
int u, v, w;
scanf("%d%d%d", &u, &v, &w);
add_edge(u, v, w);
add_edge(v, u, w);
}
spfa1(0, n - 1); spfa2(n - 1, 0);
ll ans = 0;
int len = dis1[n-1];
for (int u = 0; u<n; u++){
for (int i = head[u]; ~i; i = edge[i].nxt){
if (dis1[u] + dis2[edge[i].to] + edge[i].w == len)
ans += edge[i].w;
}
}
printf("%I64d
", ans * 2);
return 0;
}Uva1471
题意：给定一个长度为n的序列，你的任务是删除一个连续子序列，使得剩下的序列中有一个长度最大的连续上升子序列
解法：首先处理出从以i为终点的上升子序列长度，再处理出以i为起点的最长上升子序列长度，
之后我们枚举每个i，在有序表中一次性找到他前面的j，使得a[j]
#include<cstdio>
#include<set>
#include<algorithm>
#include<iostream>
#include<cassert>
using namespace std;
const int maxn = 2e5 + 5;
int a[maxn], pre[maxn], nex[maxn];
struct node {
int a, pre;
node(int a, int pre) :a(a), pre(pre){}
bool operator < (const node& rhs) const { return a < rhs.a; }
};
set<node>s;
//核心思想：处理出来pre[i]和nex[i]之后，我们就要枚举每个i，之后一次找到在i之前的
//j的位置，用j的pre加上i的nex，用这个值来更新ans；
//由于我们需要保证每次查找的j都是a[j]的值要最小且j的pre尽量长，所以每次比较完之后需要更新集合
//插入任何一个二元组是先找到插入位置，根据前一个元素判断是否需要保留，如果需要保留，就往后保留
//紫书：P242
int main(){
int T; cin >> T;
while (T--) {
int n; cin >> n;
for (int i = 0; i < n; i++)
cin >> a[i];
if (n == 1) { cout << 1 << endl; continue; }
pre[0] = 1;//以第i个元素结尾最长长度
for (int i = 1; i < n; i++) {
if (a[i - 1] < a[i])pre[i] = pre[i - 1] + 1;
else pre[i] = 1;
}
nex[n-1] = 1;//以第i个元素开头的最长长度
for (int i = n - 2; i > 0; i--) {
if (a[i] < a[i + 1])nex[i] = nex[i + 1] + 1;
else nex[i] = 1;
}
int ans = 1;
s.clear(); s.insert(node(a[0], pre[0]));
for (int i = 1; i < n; i++) {
node now = node(a[i], pre[i]);
set<node>::iterator it = s.lower_bound(now);
bool keep = true;
if (it != s.begin()) {
node last = *(--it);
int len = nex[i] + last.pre;
ans = max(ans, len);
if (last.pre >= now.pre) keep = false;
}
if (keep) {
s.erase(now); s.insert(now);//erase默认没找到就不删除
it = s.find(now); it++;
//更新后面的
while (it != s.end() && it->a > now.a && it->pre <= now.pre) { s.erase(it++); }
}
}
cout << ans << endl;
}
return 0;
}
Uva714
题意：把一个包含m个正整数的序列分成k个非空的连续子序列，使得每个正整数恰好属于一个序列，设第i个序列的个数之和s(i)，找到分配方案，使得所有s(i)的最大值尽量小。
解法：二分最小值x，二分的范围是元素最大值到所有元素的和
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
using namespace std;
typedef long long ll;
int p[10000], m, k;
int solve(ll maxp) {
int ans = 1;
ll done = 0;
for (int i = 0; i < m; i++) {
if (done + p[i] <= maxp) { done += p[i]; }
else { ans++; done = p[i]; }
}
return ans;
}
int last[1000];
void print(ll ans) {
memset(last, 0, sizeof(last));
ll done = 0;
int remain = k;
for (int i = m - 1; i >= 0; i--) {
if (done + p[i] > ans || i + 1<remain) {
last[i] = 1; remain--; done = p[i];
}
else done += p[i];
}
for (int i = 0; i < m-1; i++) {
cout << p[i] << " ";
if (last[i])cout << "/ ";
}
cout <<p[m-1]<< endl;
return;
}
int main() {
int T; cin >> T;
while (T--) {
cin >> m >> k;
ll tot;
int maxp;
tot = 0, maxp = -1;
for (int i = 0; i < m; i++) {
cin >> p[i];
tot += p[i];
maxp = max(maxp, p[i]);
}
ll l = maxp, r = tot;
while (l < r) {
ll mid = l + (r - l) / 2;
if (solve(mid) <= k)r = mid;
else l = mid + 1;
}
print(l);
}
return 0;