JZYshuraK

分类

未归档(392)

/ 注册

全部文章（共392篇）

[bzoj5118]Fib数列2_费马小定理_矩阵乘法

Fib数列2 bzoj-5118 题目大意：求Fib($2^n$)。注释：$1\le n\le 10^{15}$。想法：开始一看觉得一定是道神题，多好的题面啊？结果...妈的，模数是质数，费马小定理就tm完事了，将fib数列的通项公式列出来然后费马小定理... 最后，附上丑陋的代码......

2018-07-15

0 450

[bzoj3282]Tree_LCT

Tree bzoj-3282 题目大意：给你n个点m个操作。更改单点权值，加边，删边；查询路径异或和。注释：$1\le n,m\le 10^5$ 想法：看到了加边删边，果断想到LCT维护。至于路径异或和，我们只需要维护每个点对应splay的子树异或和，然后查询的时候直接access+spla...

2018-07-15

0 266

[bzoj2789][Poi2012]Letters_树状数组

Letters bzoj-2789 Poi-2012 题目大意：给定两个字符串A和B，每次交换A中相邻两个数。问至少交换多少次，可以将A变成B。注释：$2\le n\le 10^6$ 想法：我们发现，A中任意两个相同字符的相对位置是不会发生改变的，所以我们可以直接求逆序对即可。最后，附上...

2018-07-14

0 303

[bzoj1090][SCOI2003]字符串折叠_区间dp

字符串折叠 bzoj-1090 SCOI-2003 题目大意：我说不明白...链接注释：自己看想法：动态规划状态：dp[i][j]表示从第i个字符到第j个字符折叠后的最短长度。转移：dp[l][r]=min(r-l+1,dp[l][k]+dp[k+1][r]) 当k+1~r可以有...

2018-07-12

0 282

[bzoj1614][Usaco2007Jan]Telephone Lines 架设电话线_二分答案_最短路

Telephone Lines bzoj-1614 Usaco-2007Jan 题目大意：给你一个n个点m条边的带边权无向图，求最短路。可以选取k条边免费。注释：$1\le n\le 10^3$，$1\le m\le 10^5$ 想法：一眼分层图最短路啊！我都想出来了就上网查一下题解吧 ...

2018-07-12

0 268

[bzoj3389][Usaco2004Dec]Cleaning Shifts安排值班_最短路

Cleaning Shifts bzoj-3389 Usaco-2004Dec 题目大意：每天有n个时间段，每个时间段都必须安排一个奶牛值班。有m个奶牛，每个奶牛只有一个空闲时间s[i]~e[i]，求至少动用多少奶牛。注释：$1\le n\le 10^6$，$1\le m\le 25,000$...

2018-07-12

0 261

[bzoj4562][Haoi2016]食物链_记忆化搜索_动态规划

食物链 bzoj-4562 Haoi-2016 题目大意：给你n个点，m条边的DAG，求所有的满足条件的链，使得每条链的起点是一个入度为0的点，中点是一条出度为0的点。注释：$1\le n\le 10^5$，$1\le m\le 2*10^5$。想法：考试T2，全场切动态规划状态：...

2018-07-12

0 415

[bzoj3680]吊打XXX_模拟退火

吊打XXX bzoj-3680 题目大意：在平面上给定n个点，每个点有一个权值。请在平面上找出一个点（不一定在这n个点内找）使得这个点到n个点的距离*权值最小，即求这n个点的重心。注释：$1\le n\le 10^4$，$-10^5\le x_i,y_i\le 10^5$。想法：模拟退...

2018-07-12

0 371

长枪短炮技巧の菜刀流[处理一些问题的小方法]

杂技篇【长期更新】 1.在O(n)时间内处理出一个字符串的所有循环字符串的hash值：将字符串倍长，然后通过取模运算实现　　for(int j=0;j<=(n<<1)-1;j++) f[j+1]=f[j]*base+s[j%n]-'a'+1; 2.一个图是不是二分图的充要条...

2018-07-11

0 537

[bzoj2186][Sdoi2008]沙拉公主的困惑_数论

沙拉公主的困惑 bzoj-2186 Sdoi-2008 题目大意：求N!中与M!互质的数的个数。注释：$1\le N,M\le 10^7$。想法：显然是求$\phi(M!)$。这东西其实只需要将数据极限范围内所有的逆元崩出来就行了... ... 最后，附上丑陋的代码... ... ...

2018-07-10

0 250