题目地址
给定一个仅由小写字母组成的序列,按一定的规则排列,输出给定序列在排在所有序列中的哪里
规则是,长度短的排在前面,长度相同的,按字典序排序,而且序列是合法的当且仅当从左算起第i位的字母必须严格小于第i位后面的所有字母,即vwxyz是合法的,vwyxz是不合法的.
一个大致序列如下:
a -> 1
b -> 2
.
.
z -> 26
ab -> 27
ac -> 28
.
.
az -> 51
bc -> 52
.
.
vwxyz -> 83681
对于不合法序列,输出0
首先,我们先不考虑序列不合法的情况,那么对于一个n位的序列,其位置可能达到s=C(26,1)+C(26,2)+…+C(26,n),我们算出s的值,然后再减掉不合法的序列以及大于给定序列的其他序列的情况.假设给定序列是abcd,n=4,那么我们减掉所有以a以后字母开头的序列个数,即C(25,4),现在我们剩下的就是以a开头的不合法序列和大于abcd但小于axyz的合法序列,对于第二位,我们减掉以b以后字母为第二位的序列,即C(24,3),现在剩下的是以ab开头的不合法序列和大于abcd但小于abyz的合法序列,以此类推即可.
Memory: 132K
Time: 0MS
#include <iostream>
using namespace std;
int C(int n, int r) {
int i, j, s = 1;
if(n - r > r) r = n - r;
for(i = 0, j = 1; i < r; i++)
for(s *= n - i; j <= r && !(s % j); j++) s /= j;
return s;
}
int main() {
char s[6];
int l, i, j, res;
while(scanf("%s", s) != EOF) {
l = strlen(s);
res = 0;
for(i = 0; i < l - 1; i++)
for(j = i + 1; j < l; j++)
if(s[i] >= s[j]) {
puts("0");
goto next;
}
for(i = 1; i <= l; i++) res += C(26, i);
for(i = 0; i < l; i++) res -= C(122-s[i], l-i);
printf("%d\n", res);
next:;
}
return 0;
}
题目地址
这题着实写了大半个下午..
题目大意是求A^B中,所有因数的和模9901的值.
稍微推下公式易知,对于一个数A,若A=p1^n1 * p2^n2 * P3^n3….,其中p1,p2,p3..都是A的质因数,则其所有因数和应该为(p1^0 + p1^1 + p1^2+…+p1^n1) * (p2^0 + p2^1+…+p2^n2) * …所以A^B的所有因子和为(p1^0 + p1^1 + p1^2+…+p1^(n1*B)) * (p2^0 + p2^1+…+p2^(n2*B)) * …,根据几何级数的求和公式有,sum = (p1^(n1*B+1) – 1) / (p1-1) * (p2^(n2*B+1) – 1) / (p2 – 2) *…
题目即求sum % 9901的值.
而对于该式,我们只需用对分子的积求模,然后乘以分母对9901的逆元即可,求逆元用扩展欧几里德.
这里有一个恶心的地方,对于某个数p1,如果p1%9901的值等于1,那么套用上述公式是不正确的,因为此时相当于几何级数中的倍数为1,那样是不能套用公式的,正确的和应该为n1*B+1.
Memory: 144K
Time: 0MS
#include <iostream>
using namespace std;
const int M = 9901;
const int N = 7073;
typedef long long ll;
int p[908] = {2}, l = 1, fac[35][2], top, ans;
bool prime[N+1] = {1, 1};
void init() {
int i, j;
for(i = 3; i <= N; i += 2) {
if(!prime[i]) p[l++] = i;
for(j = 1; j <= l && i * p[j] <= N; j++) {
prime[i*p[j]] = 1 ;
if(!(i%p[j])) break;
}
}
}
void split(int n) {
int i;
top = 0;
for(i = 0; i < l; i++)
if(!(n%p[i])) {
fac[top][0] = 0, fac[top][1] = p[i];
while(!(n%p[i])) fac[top][0]++, n /= p[i];
top++;
if(n == 1 || n < N && !prime[n]) break;
}
if(n != 1) fac[top][0] = 1, fac[top++][1] = n;
}
int Pow(int a, ll b) {
int t = 1;
while(b) {
if(b & 1) t = t * a % M;
a = a * a % M;
b >>= 1;
}
return t;
}
int ex_gcd(int a, int b, int &x, int &y) {
if(!b) {x = 1; y = 0; return a;}
int ans = ex_gcd(b, a%b, x, y), t = x;
x = y;
y = t - (a / b) * y;
return ans;
}
int main() {
int a, b, res, i, res1, x, y, tmp;
init();
while(~scanf("%d%d", &a, &b)) {
split(a);
res = res1 = 1;
for(i = 0; i < top; i++) {
tmp = Pow(fac[i][1] % M, (ll)fac[i][0] * b + 1);
if(tmp == 1) res = (res * ((ll)fac[i][0] * b + 1)) % M;
else {
res *= (tmp - 1 + M) % M;
if(res >= M) res %= M;
res1 = res1 * (fac[i][1] - 1);
if(res1 >= M) res1 %= M;
}
}
ex_gcd(res1, M, x, y);
printf("%d\n", (res * ((x + M) % M)) % M);
}
return 0;
}
题目地址
for (variable = A; variable != B; variable += C)
statement;
题目给定A,B,C,问这个循环执行多少次会停止或者永远不停止.题目还给定一个k,代表当数值达到2^k时,会自动重新从0开始.
很明显,就是要我们求(A + C * x) % 2^k = B中,x的值即C*x % 2^k = B – A,即一个赤裸裸的扩展欧几里德
Memory: 132K
Time: 0MS
#include <iostream>
using namespace std;
typedef long long ll;
ll ex_gcd(ll a, ll b, ll &x, ll &y) {
if(!b) {x = 1; y = 0; return a;}
ll ans = ex_gcd(b, a%b, x, y), t = x;
x = y;
y = t - (a / b) * y;
return ans;
}
int main() {
ll a, b, c, x, y, t, s;
int k, i;
while(scanf("%lld%lld%lld%d", &a, &b, &c, &k), a || b || c || k) {
s = (ll)1 << k;
t = ex_gcd(c, s, x, y);
b -= a;
if(b % t) {
puts("FOREVER");
continue;
}
printf("%lld\n", (x * b / t % (s/t) + (s / t)) % (s / t));
}
return 0;
}
题目地址
题目大意是，给定一个小于50W位的数N，正常情况下，该数应该等于n^n,如果能找到一个n,使得n^n=N，则输出N，否则有可能是该数N中其中唯一的一位发生了错误(N的长度不变)，则应该输出-1
容易知道如果N的长度为1,则只有N＝＝1或N＝＝4才有解。
对于其他情况，首先我们知道n^n的位数应该等于w=log10(n^n)+1=nlog10(n)+1,由于数N最多为50W位，故容易得出n最大为100000,那么我们可以先二分找出n的值，然后判断n^n与N是否相等，如果相等则输出n,否则输出-1,那么如何判断相等呢
假设N原来的值为a,变化后的值为b,因为最多只可能改变一位，我们假设a+k*10^(n-1)=b,即a的第n位多了k,这里我们只假设k为正的情况，为负的同理，那么有0<=k<=9,且第n位加了k后不产生进位。我们即要判断a跟a+k*10^(n-1)是否相等，为了避免直接计算a的值，我们想到了应该对两边进行取模运算，那么应该对什么数求模，则如果发生改变，那么余数绝对不相等呢，这里我们取该数为99,那么对于n>=3有
(a+k*10^(n-1))%99 = a%99 + k * 10^(n-1)%99,因为10^(n-1)%99=1(n>=3)
所以(a+k*10^(n-1))%99 = a%99 + k %99
如果看出当k!=0时，a%99+k%99的值绝对不等于a%99的值，所以要判断n^n与N是否相等，只需判断n^n%99与N%99是否相等即可。
Memory: 808K
Time: 0.06S
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <cmath>
using namespace std;
const int M = 99;
char a[500002];
int Pow(int a, int b, int c) {
int t = 1;
while(b) {
if(b & 1) t = t * a % c;
a = a * a % c;
b >>= 1;
}
return t;
}
int main() {
int t, i, l, r, m, len, res, len1;
scanf("%d", &t);
while(t--) {
scanf("%s", a);
for(i = len = res = 0; a[i]; i++, len++) res = (res * 10 + a[i] - '0') % M;
if(len == 1) {
printf("%d\n", res == 1 ? 1 : (res == 4 ? 2 : -1));
continue;
}
l = 3, r = 100000;
while(l <= r) {
m = (l + r) >> 1;
len1 = (int)(m * log10((double)m)) + 1;
if(len1 == len) break;
if(len1 < len) l = m + 1;
else r = m - 1;
}
if(Pow(m%M, m, M) == res) printf("%d\n", m);
else puts("-1");
}
return 0;
}
比赛地址
题目其实都不是很难，但是细节要注意挺多的
Problem A: 数论+组合？
其实很容易就能得出公式为ans = (sum! / (a[0]! * a[1]! * ….*a[n-1]!)) % 200009，其中sum = a[0] + a[1] +… + a[n-1], 而难点就在于如何快速求得解。
我们先简化一下，求解ans = a / b % m的值，该式可以化为ans = ((a%m) * (x%m))%m,其中,x为b的逆元，即b * x = 1 (mod m), 容易得出，此即为求b*x + m * y = 1的解，这个可以用扩展欧几里德求解(m为素数的前提下)。
所以原题就是对除数求逆元，比赛时，有一个福大的同学很快就写出了正确的算法，可是却一直TLE或WA，在这里，对于求除数逆元，不能一个一个求逆元再乘起来，对于(a[0]!*a[1]!*…*a[n-1]!) * x = 1 (mod m),我们可以先求得a[0]!*a[1]!*…*a[n-1]!) % m 的值A,然后再去求A * x = 1 (mod m),可以知道，这样求出来的结果是等价的。
注意到数据的范围，可以一开即始预处理出1到40000内所有阶乘mod 200009的值，计算过程可能会超出32位，必须用long long,刚才说的那位同学，好像在求逆元的x%m处理上有问题，导致后面优化后的程序虽然不TLE了，可是却会出现负数造成WA。
Problem B: 题目很长，实际很水。。
Problem C: 算不上几何的几何？
这题就很简单了，也没有什么坑人的地方。给定一些圈圈，和两个点，问从一个点从到另一个点需要穿过几条弧。
这题是Topcoder上的一道题目，记得那时比赛时，算是最水的一道题了，可是不知为啥Petr竟然这题写了相当相当的长，匪疑所思，神牛也有考虑的太复杂的时候？
其实就是枚举每一个圈圈，对于每一个圈圈，如果两点都不在这个圈内或都在这个圈内，则不做任何处理，否则穿过的弧形数量+1
Problem D: 模拟题?
很有意思的一道简单模拟题。
其实，按逆时针方向进行打表，那么对于每次改变方向s,假设一开始方向为t,如果s==1，则t = (t+1)%8,如果是其他情况，则为t = (t + 1 + (s – 1) * 2) % 8 = (t + 2 * s – 1) % 8.土土模拟直到光线射出那个框为止
Problem E: 还没看，据说很恶心
Problem F: ???
其实这题应该也是很简单的，可是却是全场提交最多次，过的却很少的，相当WS的一道题，其实在其他细节的处理方面，很多同学第一次写的就都做的很好了，可是却是一直WA。其实在比赛的前几分钟，geng又对这题加了一组数据，也就是这组数据，卡住了众多的人，而这组数据很简单，就是只有一个常数。很多同学处理时，如果遇到系数为0的，都是直接忽略掉，这样在有其他项的时候是没有错，但是如果数据只有一个常数，那么他们那样处理，结果就是对该组数据没有任何输出，而这组数据其实应该是输出0.
对于为此题纠结了一个下午的同学，我替geng表示抱歉，但是这也提醒我们，要注意到对各种边界数据的考虑，往往就是那么一组数据，就是成功与失败的差别。
复赛结果：170名
残念，只做出第一道题
题目大概是求一个大于N的最小数,这个要求这个数没有相邻两位是相同的。
郁闷，一开始太兴奋了，竟然无视数据10亿的范围，只接一个一个遍历判断，瞬间第一个提交，得了将近满分，正高兴着，结果后面测试时发现最大数据会超时，顿时无语，重新用另一种方法写并提交，只得了100出头的分数，第二题跟第三题就不会了，然后就根据写的过程构造了第一题的特殊数据，结果在挑战阶段cha掉了几个人，得分上升到262.56分，就此终结。。
总结：比赛时不能太兴奋，实力要再加强，第二题不应该做不出来，继续努力！！！加油！！！！
比赛地址
这次的题目总体是比较水的，不过今天一直没在状态上，每道题平均起来都写了半小时以上-_-……….
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题目都还没看。。
Recent Comments