比赛地址
这次的题目总体是比较水的，不过今天一直没在状态上，每道题平均起来都写了半小时以上-_-……….
Problem A:
求一个二叉树以某点为开始结点时，其他点到该点的最小路径（定义为到该结点的距离乘以结点的权值)
建好二叉树后依次对每个点进行深搜，求得最小值即可。
Problem B:
USACO上的题，莫名其妙的WA，过不了，解题详见USACO
Problem C:
给定一个n*n的01矩阵，求该矩阵里大小为2*2,3*3,4*4,…,n*n的子矩阵有几个，要求这些子矩阵里元素全为1,矩阵可以有重叠，即每两个子矩阵可以共用一部分方格。
预处理出该n*n矩阵中所有以(1,1)为左上角，(i,j) {i<= i, j<=n}为右下角的矩阵中所有元素的和f[i][j],然后枚举矩阵中的每个元素，以该元素的位置(i,j)为起始位置，测试从左上角(i,j)到右下角(i+k-1,j+k-1)的矩阵的和是否等于k*k{2<=k<=n},如果相等则k*k的子矩阵增加一个。
Problem D:
给定t,n和t个系数n1,n2,n3,…nt{n1+n2+…nt=n}，求(x1+x2+…+xt)^n展开式中x1^n1*x2^n2*…*xt^nt的系数的值
转变下思想，其实题目就是一个简单的组合数学题，给定n样物品放到t个箱子中，要求箱子1中有n1个物品，箱子2中有n2个物品…求所有可能的放法总数。
所以有res = C(n,n1) * C(n-n1,n2) * C(n-n1-n2,n3)*…*(n-n1-n2…nt-1,nt)
Problem E:
1+q+q^2+q^3+……+q^(n-1) 的和对1000000007的模
注意到1<=q<=10^18,1<=n<=10^9，故简单的一个线性扫描肯定会超时。
q 1 q^n 1+q+q^2+…+q^(n-1)
我们构造一个矩阵A= 0 1,则有A^n = 0 1
故二分求B=A^n，结果存放在B[0][1]中。
Problem F:
给定两个字符串A和B，它们的距离是这样定义的，在A B这两字符串中的任意位置添加任意个空格，当添加后两个字符串相等时，从第一个字符开始比较，如果第i个字符都是非空字母，则距离加上两字母相减的绝对值，如果一个为字母一个为空格，则加上一个给定的值k,如果两个都是空格，则不用加，要求在所有添加空格的方法中，最后得出的距离值最小的即为A和B的距离，求该距离
我们构造一个二维数组f[i][j]代表当匹配到A[i],B[j]时两者的最小距离，那么有
如果将A[i],B[j]进行配对，则f[i][j] = f[i-1][j-1] + abs(A[i]-B[j])
如果将A[i],与空格配对，则f[i][j] = f[i-1][j] + k
如果将B[j]与空格配对，则f[i][j] = f[i][j-1] + k
所以状态转移为f[i][j] = min(f[i-1][j-1] + abs(A[i]-B[j]),f[i-1][j] + k,f[i][j-1] + k)
最终结果在f[la][lb]中，la,lb为字符串A,B的长度（下标从1开始）注意f[i][j]的初始问题，f[0][0]=0,
f[0][j] = j * k, f[i][0] = i * k,具体原因自己想一下即可知道。
这次题目是面向新生的，所以总体来说是比较简单的，除了B题有考到简单深搜的算法，其他都算是比较入门的题目，稍微注意点细节应该就能通过。
A: 雷达系统
用S记录合法的总时速，用T记录不合法行驶的车辆总数。
对于每个测到的时速，如果在限定范围内，则加到总时速S里，否则T增加一，最后判断不合法行驶的车辆总数是否超过总车辆数的10%,如超过则直接输出0.00,否则用S除以合法行驶的车辆数 (总车辆-T)
B: 粉刷迷宫
这题算是这些题里比较中等的一道题。
设总墙数为S。
因为要求的是从外部进去所能看到的墙壁数，所以只须先对矩阵最外围的一圈遍历一下，如果遇到墙，则S加1,如果是space,那么首先将该点标记一下，然后遍历递归遍历其四周，如果是墙，则S加1但不递归,如果是已标记则不递归，如果是space，则继续递归执行。最终S的值即为答案。
C: 跑商
模拟题。
这题或许在读题时会稍微耗点时间。
在模拟的过程中，必须记录两个值，一个是当前所买货物总量T，一个是当前总钱数S。
注意到对于地点的变化，是每5个一个循环，时间的变化是每12一个循环，所以每次模拟，对于地点的变化，只须直接模5,对时间变化模12,再找到相应的值，按题目要求的卖出再买进，然后判断是否S会大于等于原始钱数的两倍即可。
D: 圆柱体
首先注意，对于这种要用到PI的题目，为了保证精度，都取PI=acos(-1.0)。
我们知道圆柱体表面积S=2*PI*R^2+2*PI*R*H (1),体积V=PI*R^2*H (2),两者连立，易得R*S/2-PI*R^3=V,我们对f(R)=R*S/2-PI*R^3进行求导得，f’(R)=S/2-3*PI*R^2,因为要V的最大值，所以令S/2-3*PI*R^2＝0,易得R=sqrt(S/(6*PI)),再将R代入(1),(2)两式即可求出H跟V的值。
E: 陶陶抢苹果
用一个结构体记录每个陶陶的体重和其初始位置以及拿到的苹果总重量，首先将该结构体按体重降序排序，将给定苹果重量降序排序，然后依次模拟将苹果赋给相应的陶陶，最后将结构体按初始位置升序排序，输出每个陶陶拿到的苹果总重量
F: 最小非负值
咋一看很可怕的题，原来是道彻彻底底的水题。任取连续的4个数a,b,c,d，易知a+d=b+c,因而对于数列
A1,A2,…,An,我们从后往前构造，可以有 + An-3 – An-2 – An-1 + An = 0,那么到最后有4种情况
(1)刚好全部四个四个一起配对，所以数列An总和为0
(2)只剩1个，即剩下1,则和为1
(3)只剩2个，即1, 2,那么和应为-1+2=1
(4)只剩3个，即1, 2, 3,那么和应为+1+2-3=0
所以只须对给定的n对4求余，再对余数进行判断即可。
比赛地址
很多不会呀。。。orz….
A: Escape
枚举所有可能的右转次数，对于特定的右转次数，都有与之对应的几次向左，向右，向上，向下走，将这几种走法的组合数相乘，再把所有右转次数的组合数相加即可。预处理组合数O(n^2).
B,C不会
D: Blocks
用生成函数推导，因为求4种颜色中两种颜色为偶数次的排列数，故其生成函数为
(1+x^2/2!+x^4/4!+….)^2*(1+x/1!+x^2/2!+x^3/3!+….)^2
已知1+x/1!+x^2/2!+x^3/3!+….=e^x
所以上式可化成((e^x-e^(-x)/2)^2*e^(2x)
化简得e^(4x)/4-e^(2x)/2+1/4
再将该式展开，可知x^n的系数为(4^(n-1)-2^(n-1))/n!,所以所求的个数应为(4^(n-1)-2^(n-1))/n!*n!=4^(n-1)-2^(n-1)
即为该问题的解，对于该式只需二分求余即可。
话说该题的推导可以用组合数学的牛逼方法，偶是完全看不懂了
赞一下5l2MM
E: 不会
F: Training little cats
矩阵乘法，构造n+1的矩阵，观察可知，对于加1的变换，实际是将第几列相应的数全加到第n-1列上(下标0开始),置0变换，是将第几列全变为0,交换操作，是将第几列与第几列交换，所以我们完全可以手工模拟乘法过程，达到O(kn)的构造操作，注意由于交换的性质，对于这些变换操作，要从最后一个开始处理起
即对于
g 1
s 1 2
应该先就s 1 2构造，再构造g 1
然后在矩阵相乘时，注意如果相乘的两个数均为0,则不操作，这对稀疏矩阵的提速非常明显(orzTTBJ的提醒)
G: UmBasketella
最水的一道题，稍微学过立几的都会。。
H,I题目都还没看。。
很囧很囧。。。结果就不说了，Just 总结下目前会的题目。。
比赛地址
A：Accept
枚举4个点，判断是垂直，一个O(n^4)就能过
B：Choose ACMer
模拟题，注意09级比08级年轻，应该排在前面，，还有在计算最优的前n-2个分数时，，要直接用加的，不要用总的n个的和减去最差的2个，这样会造成精度问题。。
C：Heroes General Assembly
数论题。
题目即求a^b = 1 (mod c)中,b的最小值。
设b的最小值为e, 根据欧拉定理有，e | phi(c),其中phi(c)为欧拉函数，但是反过来并不成立，即不是充要条件。
所以我们先求出c的欧拉函数，然后对其分解素因子，再暴力枚举所有c的因子（不一定为素因子），取符合a^b = 1 (mod c)的最小值即可。
D：Largest Group
线段树。还没想到建树的方法。。
E：Magic String
找规律题。题目还没看。。
F：Put Coin Game
博弈题。试放所有位置的圆，求出每个table的SG值，再将所有的table的SG值求异或即可
G：Rotate rotate and rotate
几何题？？直接一个体积公式解决。注意PI要取acos(-1.0)….
H：Try
图论题。据说正解是拆点套用网络流，此方法不会-_-。偶是将每个钥匙能用几次就拆成几个点，然后建图套用二分图的最大匹配，，，如果数据过大，这方法就不行了。。。
I：Number Cutting Game
DP题。定义dp[i][j]=true代表前i个数，进行任意组合能得到余数j。那么有
if(dp[j][k]) dp[i][(k+num[j+1][i])%m] = true;{j<=i-1}
其实m为要模的数，num[j+1][i]代表数串中第j+1到第i个形成的数字对m求余的值。这个要首先通过预处理求得，否则会超时。总的复杂度为O(n^3)。
J：Number Reversing Game
搜索题。双向广搜+hash，赤裸裸的暴力。。
K：Special max_heap
组合数学？题目还没看。。。
题目地址
给定一组非降序的元素，求区间重复最多次的元素的重复次数。
貌似现在只会用线段树写，先放出线段树的方法
在每个结点存放三个信息，lf代表该结点所表示的区间最左边连续的相同元素的次数，rf代表右边连续的相同元素的次数，m代表该区间中重复最多次的元素的重复次数。
lf的取值，当为以下情况时
很明显lf等于左子结点的lf的值
当为以下情况时
很明显lf等于左子结点的lf的值加上右子结点的lf的值
容易知道rf与lf类似
对于m的求法，如果
则m=MAX{左结点的m,右结点的m}
如果
则m=MAX{左结点的m,右结点的m,左结点的rf+右结点的lf}
而在查询的过程中，需要注意一点的是，如果区间分属于某个结点的左右子结点中，且左右子结点的连接处的值是相等的，那么我们还要考虑这两部分相加的值是否会为最大，即MAX{左结点的m，右结点的m}后，还要判断MIN{左结点的rf,l-左点的右区间+1}+MIN{右结点的lf,r-右结点的左区间+1}是否会更大，为什么要分别取最小值再相加呢，因为左结点的rf只是单纯考虑其右边连续的个数，如果其个数超过给定区间的左边界，当然不能全都计算在内，所以有MIN{左结点的rf,l-左点的右区间+1}。
Memory: 5736K
Time: 750MS
#include <iostream>
using namespace std;
const int MAXN = 100001;
#define Max(a,b) ((a)>(b)?(a):(b))
#define Min(a,b) ((a)<(b)?(a):(b))
int a[MAXN], n;
struct {
int l, r, lf, rf, m;
} nod[MAXN*3];
void init(int t, int l, int r) {
if(l == r) {
nod[t].l = nod[t].r = l;
nod[t].lf = nod[t].rf = nod[t].m = 1;
return;
}
int m = (l + r) / 2, tmp, sum;
nod[t].l = l, nod[t].r = r;
init(t*2, l, m), init(t*2+1, m+1, r);
nod[t].lf = nod[t*2].lf, nod[t].rf = nod[t*2+1].rf;
tmp = Max(nod[t*2].m, nod[t*2+1].m);
if(a[nod[t*2].r] == a[nod[t*2+1].l]) {
sum = nod[t*2].rf + nod[t*2+1].lf, tmp = Max(tmp, sum);
if(a[nod[t].l] == a[nod[t*2].r]) nod[t].lf = sum;
if(a[nod[t].r] == a[nod[t*2+1].l]) nod[t].rf = sum;
}
nod[t].m = tmp;
}
int query(int t, int l, int r) {
if(nod[t].l == l && nod[t].r == r) return nod[t].m;
if(r <= nod[t*2].r) return query(t*2, l, r);
if(l >= nod[t*2+1].l) return query(t*2+1, l, r);
int q1 = query(t*2, l, nod[t*2].r), q2 = query(t*2+1, nod[t*2+1].l, r), tmp = Max(q1, q2);
if(a[nod[t*2].r] == a[nod[t*2+1].l]) tmp = Max(tmp, Min(nod[t*2].r-l+1, nod[t*2].rf)+Min(r-nod[t*2+1].l+1, nod[t*2+1].lf));
return tmp;
}
int main() {
int q, i, x1, x2;
while(scanf("%d", &n), n) {
scanf("%d", &q);
for(i = 1; i <= n; i++) scanf("%d", &a[i]);
init(1, 1, n);
while(q--) {
scanf("%d%d", &x1, &x2);
printf("%d\n", query(1, x1, x2));
}
}
return 0;
}
题目地址
给定一棵树，求当该树以某点为根时的最大树高，并输出满足最大树高的最小节点
根据许多大牛的方法，一次以任意顶点进行搜索找到最深的顶点，再以该顶点搜索一次即可，不明白为啥这样-_-
本来想直接开个数组，发现那样实在太大了，又懒得写链表，还是用vector方便些。。。
发现速度好慢。。囧。。
#include <iostream>
#include <vector>
using namespace std;
const int N = 100000;
vector<int>a[N+1];
int n, height[N+1];
void dfs(int l) {
for(int i = 0; i < a[l].size(); i++)
if(height[a[l][i]] == -1) {
height[a[l][i]] = height[l] + 1;
dfs(a[l][i]);
}
}
int solve(int l) {
int i, j;
memset(height, 0xff, sizeof(height));
height[l] = 1, dfs(l);
for(i = 2, j = 1; i <= n; i++) if(height[j] < height[i]) j = i;
return j;
}
int main() {
int i, j, x1, x2;
while(scanf("%d", &n) != EOF) {
for(i = 1; i <= n; i++) a[i].clear();
for(i = 1; i < n; i++) {
scanf("%d%d", &x1, &x2);
a[x1].push_back(x2);
a[x2].push_back(x1);
}
i = solve(1), j = solve(i);
printf("%d %d\n", i < j ? i : j, height[j]);
}
return 0;
}
题目地址
题目大意是，给定n个数，每次选择2个数（取出后不放回），求出两数之差的平方，累加，选k对(k<=n/2),问最终累加之和最小为多少
先对n个数排序，因为结果要求最小，那么每次择时，只能选择相邻的两个数，只有这样，最终的差才可能最小，构造dp[i][j],代表从1到n个物品中选择k对，那么状态转移方程为
dp[i][j]=Min{dp[i-2][j-1]+a[i-1],dp[i-1][j]}
其中a[i-1]存放的是第i与第i-1个数的差的平方。
#include <iostream>
#include <algorithm>
using namespace std;
#define Min(a,b) ((a) < (b) ? (a) : (b))
#define INF 2100000000
int dp[2001][1001];
int main() {
int i, j, n, k, a[2001];
while(scanf("%d%d", &n, &k) != EOF) {
for(i = 1; i <= n; i++) scanf("%d", &a[i]);
sort(a+1, a+1+n);
for(i = 1; i < n; i++) a[i] = (a[i]-a[i+1]) * (a[i]-a[i+1]);
for(i = 0; i <= n; i++)
for(j = 1; j <= k; j++)
dp[i][j] = INF;
for(i = 0; i <= n; i++) dp[i][0] = 0;
for(i = 2; i <= n; i++)
for(j = 1; j * 2 <= i; j++)
dp[i][j] = Min(dp[i-2][j-1]+a[i-1], dp[i-1][j]);
printf("%d\n", dp[n][k]);
}
return 0;
}
题目地址
题目大意是给出一系列奶牛的比赛列表，如果奶牛A战胜奶牛B，那么奶牛A的排名就在奶牛B的前面，给出一系列A beat B的列表，计算出有多少只奶牛能够确认它们的排名位置
假设有n只奶牛，那么某只牛的排名能确定的条件是该牛打败的牛数加打败该牛的数之和等于n-1,构造出图求每个顶点的入度与出度即可
#include <iostream>
using namespace std;
int main() {
int n, m, i, j, k, x1, x2, d, ans;
bool a[101][101];
while(cin >> n >> m) {
memset(a, 0, sizeof(a));
while(m--) cin >> x1 >> x2, a[x1][x2] = true;
for(k = 1; k <= n; k++)
for(i = 1; i <= n; i++)
for(j = 1; j <= n; j++)
a[i][j] = a[i][j] || a[i][k] && a[k][j];
for(i = 1, ans = 0; i <= n; i++) {
for(j = 1, d = 0; j <= n; j++) {
if(a[i][j]) d++;
if(a[j][i]) d++;
}
if(d == n-1) ans++;
}
cout << ans << endl;
}
return 0;
}
Recent Comments