例
D为区域 \(x^2+y^2\le t^2\)，\(f(0,0)=4\)
\[\lim_{t\to 0}\frac{\iint_Df(x,y)dxdy}{t-\ln(1+t)}\]
或
\[\lim_{r\to 0}\frac{\int^r_0tf(r^2-t^2)}{\iint_{x^2+y^2\le r^2}\cos(x+y)d\delta}\]
解
如果出现二重积分，没法直接求导，怎么办呢？当然是通过中值定理将二重积分转换为函数的形式。
例如：\(\iint_Df(x,y)dxdy=f(a,b)\pi r^2\)，而因为r趋于0，所以 \(f(a,b)=f(0,0)=4\)，再消去t，即可算出结果。
同理，第二个例子分母可转化为 \(\cos(a+b)\pi r^2=\cos(0)\pi r^2=\pi r^2\)。
上周日的pat圆满结束，达到了预定目标100分，撒花！
甲级第一题有一点难度，后面三题都很简单。刚开始写第一题的时候，心中纳闷，第一题就这么诡异后面怎么办？有难度！于是写了半小时没写出来，运行超时，然后开始写后面的，想着回头再写。
没想到后面啪啪啪写完一道两道三道，原来只是第一题难一点，后面都没有难度，幸好先跳了，保存了良好的心态。剩下一个半小时，怎么会写不出第一道！
第一题换了三种思路，第一遍用数组排列组合递归计算，虽然思路还行，但是数组拷贝想想也会超时，pass；第二遍想着，暴力解会不会过，然后写了个简单粗暴的循环遍历，不出意外的超时了，pass；第三遍改进了第一遍的方法，我还是觉得这道题就是个排列组合的题，于是优化了一下，去掉了数组，从高位往低位递归的进行计算，最后排序输出，折腾了一会儿，终于过了，交卷走人。
第一题的难点在于，给的数据量很大，很容易超时，而且自己根本无法构造测试数据，硬核地检测你逻辑的正确性。如果做一大堆骚操作做特例判断哪些数符合条件，哪些数跳过，往往费事又无法考虑周全，反而应该停一停，换个思路，做出更为通用简洁的算法。 PS：当时做完所有题，会回到题目列表，一看第一题通过率0.02……可怕。以前做的真题最低也是0.2
通过pat的练习，学到的最重要的一个思想就是，想不清了、乱了、复杂了，立刻换种思路，不要缝缝补补原先的程序，往往只有好处。不要被原先的思路局限，换换角度，往往能找到令自己都惊叹的思路。
至于算法什么的，都是附带的，随便写写就会了。关键还是看问题的思路、经验。
考前一共做了58道真题，前面39道，后面49道，前面的难，后面的简单。
如果你是新手但以前好好学习敲过一些代码，还是建议先做前面的，再做后面的，先被奇怪的题恶心一下，积攒一点经验，再做后面的近些年的原题，会得心应手不少，舒服极了。经验还是很重要的，有些题一看就知道敲过几遍，就不慌了。
至于要不要做完，如果你闲的话，随你，可以做，但没有必要。做过几十道题，我就懒得做了。知道一些题目套路，刷多了我自认为也只是浪费时间没有什么提高。到时候想不到的还是想不到的。
当然，如果做了几十道题没啥感觉还是觉得很懵逼，或者以前没怎么写过代码的，还是建议多写一点，能写多少是多少。
还有考试前所有算法还是要看看，我就翻了翻数据结构的书，看了看算法，然后这次考试那道图的题虽然我练习的时候从来没写过那个算法，但算法我会啊，挠了挠头就大致不离的写出来了，一下就过了。但如果你因为没练到，就压根没听说过这个算法，就只能呵呵了。
后面几道题没什么可以说的，就说说第一题吧，其实也没什么难度，关键是想不想得到，理不理的清。
"Forever number" is a positive integer A with K digits, satisfying the following constrains:
the sum of all the digits of A is m;
the sum of all the digits of A+1 is n; and the greatest common divisor of m and n is a prime number which i s greater than 2.
Now you are supposed to find these forever numbers.
Each input file contains one test case. For each test case, the first line contains a positive integer N (≤5). Then N lines follow, each gives a pair of K (3<K<10) and m (1< m<90), of which the meanings are given in the problem description.
For each pair of K and m, first print in a line Case X, where X is the case index (starts from 1). Then print n and A in the following line. The numbers must be separated by a space. If the solution is not unique, output in the ascending order of n. If still not unique, output in the ascending order of A. If there is no solution, output No Solution.
1 | 2 |
1 | Case 1 |
给定数字的位数K，若存在K位的数，它的每一位加起来为m，且这个数+1后每一位加起来为n，而m和n的最大公因数是一个大于2的素数，那么输出所有这种数。
给定K和m。
1. 假设首位为1，则第2位到第K位加起来的数只能是m-1才能符合要求。
1. 假设第2位为1，则第3位到第k位加起来的数只能是m-1-1才能符合要求。
1. 假设第三位为1，则第4位到第K位加起来只能是m-1-1-1才能符合要求。
1. ......
可以看出，递归的思路十分简单，你给我一个K位数，要他们每一位加起来是m，那么我定了这个数最前面一位为a，后面跟着那个K-1位的数加起来只能是剩下来的m-a。如果到某一位剩下来的额度变成0了，那前面的数是之前确定的，后面的数就只能是000...（用0补齐，当然如果到最后一位才用完自然就没有0结尾了）。
然后再判断这个数的m和n是否符合条件即可。
1 | #include <vector> |
通常替换为：\(2\cos^2\frac{x}{2}\)
> \(1+\cos x=2\cos^2\frac{x}{2}\)
整个数列的和函数无法给出，但注意\(\frac{1}{n}\ge\int^{n+1}_n \frac{1}{x}dx\)，这样数列就转化为首尾相连的\(\int \frac{1}{x}dx\)，与\(\ln x\)建立起关系。
因为夹逼关键是要凑出\(\frac{n+1}{n}\)的形式，因此\(1+i^2\)应该变形为\((1+i)^2\)，形式较为统一，才会出现极限相同的情况。另一侧，可以考虑变为\(i^2\)，这样两侧比较可能夹逼成功。
若难以直接表示出来，可以先观察函数的形式，若为奇函数，将\(-x\)代入，可以得到
\[\begin{cases} y=f(x) \\ -y=f(-x) \end{cases}\]
的形式，再对复杂的成分进行操作，解出\(x=\phi (y)\)的形式。
那么通常在求极限的过程中会用到导数的定义的形式转化，即：
\[f'(a)=\frac{f(x)-f(a)}{x-a}\]
The lowest common ancestor (LCA) of two nodes U and V in a tree is the deepest node that has both U and V as descendants.
Given any two nodes in a binary tree, you are supposed to find their LCA.
对两边进行积分即可。
注意：\(\ln y = \ln x + \ln c \to y = cx\)
\[\frac{dy}{dx}=f(\frac{y}{x})\]
令\(\frac{y}{x}=u\)，\(y=xu\)，\(\frac{dy}{dx}=u+\frac{du}{dx}\)。
\[\frac{du}{f(u)-u}=\frac{dx}{x}\]
对两边进行积分，再将\(\frac{y}{x}=u\)带回。
形如：
\[\frac{dy}{dx}+P(x)y=Q(x)\]
通解为：
\[y=e^{-\int P(x)dx}(\int Q(x)e^{\int P(x)dx}dx+C)\]
两边对x反复积分。
令\(y'=p,y''=\frac{dp}{dx}\)，降阶，解两次微分方程。
令\(y'=p,y''=p\frac{dp}{dy}\)，降阶，解两次微分方程。
注意：若需要两边同时约去p，记得考虑p是否等于0。
例如\(y''+ay'+by=0\)
根据特征方程\(\lambda ^2+a\lambda+b=0\)解出特征值。
若特征值不同，则通解为\(C_1e^{\lambda_1x}+C_2e^{\lambda_2x}\)
若特征值相同，则通解为\((C_1+C_2x)e^{\lambda x}\)
若存在虚根……
Shopping in Mars is quite a different experience. The Mars people pay by chained diamonds. Each diamond has a value (in Mars dollars M\(\$\)). When making the payment, the chain can be cut at any position for only once and some of the diamonds are taken off the chain one by one. Once a diamond is off the chain, it cannot be taken back. For example, if we have a chain of 8 diamonds with values M$$$3, 2, 1, 5, 4, 6, 8, 7, and we must pay M$15. We may have 3 options:
Cut the chain between 4 and 6, and take off the diamonds from the position 1 to 5 (with values 3+2+1+5+4=15). Cut before 5 or after 6, and take off the diamonds from the position 4 to 6 (with values 5+4+6=15). Cut before 8, and take off the diamonds from the position 7 to 8 (with values 8+7=15). Now given the chain of diamond values and the amount that a customer has to pay, you are supposed to list all the paying options for the customer.
If it is impossible to pay the exact amount, you must suggest solutions with minimum lost.
例
给定直线方程L与平面方程\(\Pi\)，问投影方程？
解
根据直线方程L计算直线方向向量s，根据平面方程计算平面法向量p，则\(s\times p\)即可得到垂直与平面且过直线L的新平面法向量。与平面\(\Pi\)联立即为投影方程的直线方程。
例
过点\(P(-1,0,4)\)且与平面\(3x-4y+z+10=0\)平行，又与直线\(L:\frac{x+1}{1}=\frac{y-3}{1}=\frac{z}{2}\)相交的直线方程为______
解
先过点P做平面的平行面\(3(x+1)-4y+(z-4)=0\)，再求它与直线的交点\(Q(15,19,32)\)，最后求直线的方向向量（由点P指向Q），即可得到直线方程。
例
\(L_1:\frac{x-1}{-1}=\frac{y}{2}=\frac{z+1}{1}\),\(L_2:\frac{x+2}{0}=\frac{y-1}{1}=\frac{z-2}{-2}\)
解
\(M_1\ in\ L_1,\ M_2\ in\ L2,\ (s_1\times s_2)\cdot M_1M_2=0\)意味着共面，否则不共面。
例
平面\(x-2y+z=12\)，点 \(P(1,0,-1)\)，求P的对称点。
解
可知平面法向量\(n\)为\((1,-2,1)\)，即为过点 \(P\) 垂直于平面的直线的法向量，因此该垂直直线为 \(\frac{x-1}{1}=\frac{y}{-2}=\frac{z+1}{1}\)。
接下来计算与平面交点：将直线方程转化为参数形式，带入平面方程中求得t，即可算出交点。
将 \(P\) 关于交点对称，即算得对称点。
Given a string, you are supposed to output the length of the longest symmetric sub-string. For example, given Is PAT&TAP symmetric?, the longest symmetric sub-string is s PAT&TAP s, hence you must output 11.
To prepare for PAT, the judge sometimes has to generate random passwords for the users. The problem is that there are always some confusing passwords since it is hard to distinguish 1 (one) from l (L in lowercase), or 0 (zero) from O (o in uppercase). One solution is to replace 1 (one) by @, 0 (zero) by %, l by L, and O by o. Now it is your job to write a program to check the accounts generated by the judge, and to help the juge modify the confusing passwords.
Each input file contains one test case. Each case contains a positive integer N (≤1000), followed by N lines of accounts. Each account consists of a user name and a password, both are strings of no more than 10 characters with no space.
For each test case, first print the number M of accounts that have been modified, then print in the following M lines the modified accounts info, that is, the user names and the corresponding modified passwords. The accounts must be printed in the same order as they are read in. If no account is modified, print in one line There are N accounts and no account is modified where N is the total number of accounts. However, if N is one, you must print There is 1 account and no account is modified instead.
1 | 3 |
1 | 2 |
1 | 1 |
1 | 2 |
1 | There are 2 accounts and no account is modified |
送分题，快乐 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50#include <iostream>
#include <string>
#include <vector>
using namespace std;
struct userlog {
string name, pwd;
};
int main() {
int N;
cin >> N;
vector<userlog> list;
for (int i = 0; i < N; i++) {
string name, pwd;
cin >> name >> pwd;
bool m = false;
for (int j = 0; j < pwd.length(); j++) {
if (pwd.at(j) == '1') {
pwd.at(j) = '@';
m = true;
} else if (pwd.at(j) == '0') {
pwd.at(j) = '%';
m = true;
} else if (pwd.at(j) == 'l') {
pwd.at(j) = 'L';
m = true;
} else if (pwd.at(j) == 'O') {
pwd.at(j) = 'o';
m = true;
}
}
if (m == true) {
list.push_back({name, pwd});
}
}
if (list.size() == 0) {
if (N == 1) {
cout << "There is 1 account and no account is modified";
} else {
cout << "There are " << N << " accounts and no account is modified";
}
} else {
cout << list.size() << endl;
for (auto it = list.begin(); it != list.end(); it++) {
cout << it->name << " " << it->pwd << endl;
}
}
return 0;
}
One way that the police finds the head of a gang is to check people's phone calls. If there is a phone call between A and B, we say that A and B is related. The weight of a relation is defined to be the total time length of all the phone calls made between the two persons. A "Gang" is a cluster of more than 2 persons who are related to each other with total relation weight being greater than a given threthold K. In each gang, the one with maximum total weight is the head. Now given a list of phone calls, you are supposed to find the gangs and the heads.