noip 2014 day1
总：忘了快速幂，离散化不熟，读不懂题（其实还是知识点不熟，基础不牢吧）
1.转圈游戏
读题可以发现
0->m m = ( 0+m)%n
1->m+1 m+1 = (m+1)%n
... ...
n-m->0 0 = (n-m+m)%n
n-m+1->1 1 = (n-m+1+m)%n
哇塞好像发现了什么不得了的事情
某人转一次之后的位置编号就是现在的位置编号加上m再对n取模
好啦，题目给了总人数n，给了m，给了转的总轮数10k，还给了某人当前位置编号x
emmm....好像不太对，k<109，所以......轮数是<10k^9 的.....这数有点大啊....
emm....嗷我突然想起来一个小剪枝：
他们转转转总会有转到原位置的一次吧，嗯对，那就先找到他转到原位置需要几轮，再用总轮数对它取模，
得到的就是实际需要看的轮数了，因为那些转转转都回到了原位置等于白转
所以，我就打了这样的代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,m,k,x,now/*现在在几号位置*/,per/*转回原位置需要的轮数*/;
ll tot=1;//去掉转回原位置的所有轮数，剩余实际需要看的
int main(){
scanf("%d%d%d%d",&n,&m,&k,&x);
for(int i=0;i<n;i++){
now=(now+m)%n;
per++;
if(now==0) break;
}
for(int i=1;i<=k;i++)
tot=tot*10%per;
while(tot--)
x=(x+m)%n;
printf("%d",x);
return 0;
}
然后，成功T了一个点。。。
然鹅，，，快速幂啊！！！也不用取余了，直接快速幂求10k，再套用公式，只要随时取模，就不会爆。。米有想到快速幂
某人转一次之后的位置编号就是现在的位置编号加上m再对n取模，转10k 就是现在的位置编号加上m的10k 次方就好了
这样就A了嘛。。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,m,k,x;
ll ans;
int qpow(int a, int b, int q) {
ll s = 1;
while (b) {
if (b & 1)
s = s * a % q;
a = (ll)a * a % q;
b >>= 1;
}
return s;
}
int main(){
scanf("%d%d%d%d",&n,&m,&k,&x);
ans=( x%n + m%n * qpow(10,k,n)%n ) %n;
printf("%lld",ans);
return 0;
}
2.火柴排队
就是让a,b数组中第i大的两个对应，答案就是最小的了
关键关键！u[b[i].xu]=a[i].xu
这利用了下标的单调升序。
可以发现u数组下标都是1~n，b数组中每个数的顺序也都是1~n的正整数，a数组同样如此。
那么对u数组进行归并排序之后，可以发现u数组中的值就是：u[1]=1,u[2]=2......u[n]=n对吧？
那么也就是说，对u数组进行归并排序就是为了让u[i]=i，也就是说，让b数组中第i小的数和a数组中第i小的数在同一个位置。
再加上归并排序模板就好了哈哈
#include<bits/stdc++.h>
using namespace std;
const int mod=99999997;
const int N=1000005;
int n,u[N],v[N];
long long cnt;
struct node{
int h,xu;
}a[N],b[N];
bool cmp(node x,node y) { return x.h < y.h;}
void merge_sort(int l, int r) { //归并排序模板呐~~哈哈
if(l<r) {
int mid=(l+r)/2;
merge_sort(l,mid);
merge_sort(mid+1,r);
int k=l;
int p=l,q=mid+1;
while(p<=mid||q<=r){
if(q>r||(p<=mid&&u[p]<=u[q]))
v[k++]=u[p++];
else {
v[k++]=u[q++];
cnt += (mid-p+1); //将逆序对的个数累加起来
cnt %= mod;
}
}
for (int i=l;i<=r;i++)
u[i]=v[i];
}
}
int main(){
freopen("match.in","r",stdin);
freopen("match.out","w",stdout);
scanf("%lld",&n);
for(int i=1;i<=n;i++){
scanf("%d",&a[i].h);
a[i].xu=i;
}
sort(a+1,a+n+1,cmp);
for(int i=1;i<=n;i++){
scanf("%d",&b[i].h);
b[i].xu=i;
}
sort(b+1,b+n+1,cmp);
for(int i=1;i<=n;i++)
u[b[i].xu]=a[i].xu;
merge_sort(1,n);
printf("%lld",cnt);
return 0;
}
3.货车运输
题目描述
A国有n座城市，编号从 1到n，城市之间有 m 条双向道路。每一条道路对车辆都有重量限制，简称限重。现在有 q 辆货车在运输货物， 司机们想知道每辆车在不超过车辆限重的情况下，最多能运多重的货物。
输入格式
第一行有两个用一个空格隔开的整数n,m，表示 A 国有n 座城市和 m 条道路。
接下来 m行每行3个整数 x,y,z，每两个整数之间用一个空格隔开，表示从 x号城市到y号城市有一条限重为 z 的道路。注意： ** x 不等于 y，两座城市之间可能有多条道路 ** 。
接下来一行有一个整数 q，表示有 q 辆货车需要运货。
接下来 q 行，每行两个整数 x、y，之间用一个空格隔开，表示一辆货车需要从 x 城市运输货物到 y 城市，注意： ** x 不等于 y ** 。
输出格式
共有 q 行，每行一个整数，表示对于每一辆货车，它的最大载重是多少。如果货车不能到达目的地，输出−1。
这个。。emmm...不会。。实际上题目也没太读懂。。
求助了yxt dalao，终于理解了题意，但做法大体会了一点，还是好多点不懂
noip 2015
day1总：
一开始，，文件夹交多了。。。
重交了一遍。。
发现，freopen写错了。。
并查集没学好，不会并查集判环
模拟。。。好复杂
1.神奇的幻方
就是裸裸的的模拟吧（我是这样做的）
map1存的幻方上的数，used看有没有填过
嗯，就这样，再看题目怎么说的，怎么打就好了
2.信息传递
。。没有做出来，原本想用vector把每一轮每个人收到的生日信息，都记下来，遇到自己的生日就结束了
但不会做。。。
看了下题解，还没看懂，题解好多用了并查集判环，搞了半天才弄懂
/*如果有两个点祖先节点相同，那么就可以
构成一个环，长度为两个点到祖先节点长度之和+1*/
#include<bits/stdc++.h>
using namespace std;
const int N = 200003;
int n, t, fa[N]/*祖先节点*/, d[N]/*到祖先的路径长*/, minn;
int find(int x) {
if (fa[x] != x) {
int last = fa[x]; //不能先改d
fa[x] = find(fa[x]); //更新祖先节点
d[x] += d[last]; //更新路径长
}
return fa[x];
}
void check(int a,int b) { //判环
int x = find(a), y = find(b);
if(x != y) { //不是环，则连接两点，更新父节点和路径长
fa[x] = y;
d[a] = d[b] + 1;
} else { //x=y时，形成环，更新最小环长度
minn = min(minn, d[b] + 1); //更新最小环长度
}
return;
}
int main(){
scanf("%d", &n);
for (int i = 1; i <= n; i++)
fa[i] = i;
minn = 0x7777777;
for (int i = 1; i <= n; i++) {
scanf("%d", &t);
check(i, t);
}
printf("%d", minn);
return 0;
}
3.斗地主
额，，这个毒瘤模拟。。。这个情况分的很蒙
前两个做了好长时间（虽然第二题还没做出来），然后，第三题就放弃了
到现在还没做出来。。
day2总：
emmm...二分不太会，，，导致第一题做了好久
看了下第二题，得出结论：不会。。直接部分分吧，就打了个k=1的，但是我发现，有时候对，有时候不对，最终还是得了10分
第三题，我就直接看字任务吧，发现有m=1的，这样直接找两个点之间的最短路，然后减去路径上的最大边权，就好了吧
然后我开始打。。。打着打着，发现。。。最短路不会打。。。
1.跳石头
二分
[ 使用二分的情况：
满足两个条件。一个是有界，一个是单调。
如果题目规定了有“最大值最小”或者“最小值最大”的东西，那么这个东西应该就满足二分答案的有界性（显然）和单调性（能看出来）。 ]
二分跳跃距离，然后把这个跳跃距离“认为”是最短的跳跃距离，然后去以这个距离为标准移石头。使用一个check判断这个解是不是可行解。如果这个解是可行解，那么有可能会有比这更优的解，那么我们就去它的右边二分。为什么去右边？答案是，这个区间是递增的 ，而我们求的是最短跳跃距离的最大值，显然再右边的值肯定比左边大，那么我们就有可能找到比这更优的解，直到找不到，那么最后找到的解就有理由认为是区间内最优解。反过来，如果二分到的这个解是一个非法解，我们就不可能再去右边找了。因为性质，右边的解一定全都是非法解。那么我们就应该去左边找解。整个过程看起来很像递归，这个过程可以递归写， 也可以写成非递归形式.
check函数:想办法检测这个解是不是合法。判断如果以这个距离为最短跳跃距离需要移走多少块石头，先不必考虑限制移走多少块，等全部拿完再把拿走的数量和限制进行比对，如果超出限制，那么这就是一个非法解，反之就是一个合法解.
可以去模拟这个跳石头的过程。开始你在i(i=0)位置，我在跳下一步的时候去判断我这个当前跳跃的距离，如果这个跳跃距离比二分出来的mid小，那这就是一个不合法的石头，应该移走。为什么？我们二分的是最短跳跃距离，已经是最短了，如果跳跃距离比最短更短岂不是显然不合法，是这样的吧。移走之后要怎么做？先把计数器加上1，再考虑向前跳啊。去看移走之后的下一块石头，再次判断跳过去的距离，如果这次的跳跃距离比最短的长，那么这样跳是完全可以的，我们就跳过去，继续判断，如果跳过去的距离不合法就再拿走，这样不断进行这个操作，直到i = n+1，为啥是n+1？河中间有n块石头，显然终点在n+1处。
模拟完这个过程，我们查看计数器的值，这个值代表的含义是我们以mid作为答案需要移走的石头数量，然后判断这个数量 是不是超了就行。如果超了就返回false，不超就返回true。
2.子串
DP
动态转移方程
-
f[i][j][k][0]=f[i-1][j][k][0]+f[i-1][j][k][1]，翻译是 如果第i位不使用，那么方案数就是 第i-1位未使用时，前i-1位匹配前j位使用k个子串 + 第i-1位使用时，前i-1位匹配前j位使用k个子串。
-
**（a[i]==b[j]）f[i][j][k][1]=f[i-1][j-1][k-1][0]+f[i-1][j-1][k][1]+f[i-1][j-1][k-1][1] 翻译是 如果第i位使用，意味着a[i]==b[j]，那么方案数就是 第i-1位未使用而第i位作为一个新子串 + 第i位和前面连在一起，不单独使用 + 第i-1位使用了，但第i位仍作为一个新子串。
这样转移方程就出来了。
我们再来思考边界条件。边界条件两种情况。
-
对于A子串前i位，匹配B串第1个字符，那么只可能使用1个字符串，这种情况如果第i位不进行匹配，那么方案数就是之前所有能与第1位匹配的字符，所以f[i][1][1][0]=sum(a[1~i-1]==b[1])。
-
同上，但如果B串第一位和A串第一位匹配了话，那么f[i][1][1][1]=1是显然的。
#include<bits/stdc++.h> using namespace std; const int mod = 1e9 + 7; int n, m, k; char a[1005], b[205]; int f[2][201][201][2], s, now, pre=1;//s是用来记录之前有多少个A串字符能和B串第一个字符匹配 int main(){ scanf("%d %d %d", &n, &m, &k); scanf("%s %s", a + 1, b + 1); for (int i = 1; i <= n; i++){ swap(now, pre); //交换，只要i改变 f[now][1][1][0] = s;//边界1 if (a[i] == b[1]) { f[now][1][1][1] = 1; s++;//边界2，解决了s统计的问题 } for (int j = 2; j <= m; j++) for (int t = 1; t <= k; t++){ if (a[i] == b[j]) //第i位用 f[now][j][t][1]=((f[pre][j-1][t-1][1]+f[pre][j-1][t][1])%mod+f[pre][j-1][t-1][0])%mod; //此时有i-1用或不用，i与前面相连或不相连，但i-1不用时，i不可能与前面相连了，所以共三种情况 f[now][j][t][0] = (f[pre][j][t][0] + f[pre][j][t][1]) % mod; //第i位不用时，包括i-1用和i-1不用 } for(int j = 1; j <= m; j++) for(int t = 1; t <= k; t++) f[pre][j][t][1] = f[pre][j][t][0] = 0;//清空。。 //滚动数组,用前一个状态来代替后一个状态,后一个状态需要现在的状态，但前一个状态就不需要了。。 } printf("%d", (f[now][m][k][1] + f[now][m][k][0]) % mod); return 0; }
3.运输计划
这个，，据说是LCA（求链长） + 二分
但我还不会。。