Day1
T1神奇的幻方
一道简单异常的小模拟&＃xff0c;我们只需要确定数字1的位置&＃xff0c;然后根据题意枚举即可&＃xff0c;简简单单就A了&＃xff0c;什么也不卡。
然而这题&＃xff0c;我刚开始学OI的时候&＃xff0c;因为当时比较蠢&＃xff0c;被这题花式吊打啊....根本不会啊.....
ε&＃61;(´ο&＃xff40;*)))唉又想起没学OI的自己了..
虽然题简单&＃xff0c;还是惯例丢代码
1 #include
2 using namespace std;
3 const int maxn &＃61; 60;
4 int a[maxn][maxn];
5 int n, x, y;
6
7 inline int read() {
8 int x &＃61; 0, y &＃61; 1;
9 char ch &＃61; getchar();
10 while(!isdigit(ch)) {
11 if(ch &＃61;&＃61; &＃39;-&＃39;) y &＃61; -1;
12 ch &＃61; getchar();
13 }
14 while(isdigit(ch)) {
15 x &＃61; (x <<1) &＃43; (x <<3) &＃43; ch - &＃39;0&＃39;;
16 ch &＃61; getchar();
17 }
18 return x * y;
19 }
20
21 int main() {
22 n &＃61; read();
23 x &＃61; 1, y &＃61; n / 2 &＃43; 1;
24 a[x][y] &＃61; 1;
25 for(register int i &＃61; 2; i <&＃61; n * n; &＃43;&＃43;i) {
26 if(x &＃61;&＃61; 1 && y !&＃61; n) {
27 x &＃61; n, y &＃43;&＃61; 1;
28 a[x][y] &＃61; i;
29 }
30 else if(x !&＃61; 1 && y &＃61;&＃61; n) {
31 x -&＃61; 1, y &＃61; 1;
32 a[x][y] &＃61; i;
33 }
34 else if(x &＃61;&＃61; 1 && y &＃61;&＃61; n) {
35 x &＃43;&＃61; 1;
36 a[x][y] &＃61; i;
37 }
38 else if(x !&＃61; 1 && y !&＃61; n) {
39 if(!a[x - 1][y &＃43; 1]) {
40 x -&＃61; 1, y &＃43;&＃61; 1;
41 a[x][y] &＃61; i;
42 }
43 else if(a[x - 1][y &＃43; 1]) {
44 x &＃43;&＃61; 1;
45 a[x][y] &＃61; i;
46 }
47 }
48 }
49 for(register int i &＃61; 1; i <&＃61; n; &＃43;&＃43;i) {
50 for(register int j &＃61; 1; j <&＃61; n; &＃43;&＃43;j)
51 printf("%d ", a[i][j]);
52 printf("\n");
53 }
54 return 0;
55 }
T2信息传递
大意就是说一堆人会一直传话&＃xff0c;形成一个环&＃xff0c;问你最小的环里有多少个人
显然你可以直接tarjan跑强联通分量&＃xff0c;当然你也可以跑并查集等做法做
并查集写法简单讲就是在路径压缩同时维护环的大小&＃xff0c;对于给出的传递者与被传递者&＃xff0c;判断是不是一个集合里的&＃xff0c;不是就合并
是就更新答案
1 #include
2 #define ll long long
3 #define uint unsigned int
4 #define ull unsigned long long
5 using namespace std;
6 const int maxn &＃61; 200010;
7 const int inf &＃61; 1000000007;
8 int t, fa[maxn];
9 int dis[maxn], ans;
10 int n;
11
12 inline int read() {
13 int x &＃61; 0, y &＃61; 1;
14 char ch &＃61; getchar();
15 while(!isdigit(ch)) {
16 if(ch &＃61;&＃61; &＃39;-&＃39;) y &＃61; -1;
17 ch &＃61; getchar();
18 }
19 while(isdigit(ch)) {
20 x &＃61; (x <<1) &＃43; (x <<3) &＃43; ch - &＃39;0&＃39;;
21 ch &＃61; getchar();
22 }
23 return x * y;
24 }
25
26 int getfather(int x) {
27 if(x &＃61;&＃61; fa[x]) return x;
28 int son_in_son &＃61; fa[x];
29 fa[x] &＃61; getfather(fa[x]);
30 dis[x] &＃43;&＃61; dis[son_in_son];
31 return fa[x];
32 }
33
34 int main() {
35 // freopen("message.in", "r", stdin);
36 // freopen("message.out", "w", stdout);
37 n &＃61; read();
38 for(register int i &＃61; 1; i <&＃61; n; &＃43;&＃43;i) fa[i] &＃61; i;
39 ans &＃61; inf;
40 for(register int i &＃61; 1; i <&＃61; n; &＃43;&＃43;i) {
41 t &＃61; read();
42 int u &＃61; getfather(i), v &＃61; getfather(t);
43 if(u !&＃61; v) {
44 fa[u] &＃61; v;
45 dis[i] &＃61; dis[t] &＃43; 1;
46 }
47 else ans &＃61; min(ans, dis[i] &＃43; dis[t] &＃43; 1);
48 }
49 printf("%d\n", ans);
50 return 0;
51 }
tarjan就更简单了&＃xff0c;跑强连通分量&＃xff0c;统计每个环中节点的大小&＃xff0c;然后找最小的大小不为1环的就好了
1 #include
2 #define ll long long
3 #define uint unsigned int
4 #define ull unsigned long long
5 using namespace std;
6 const int maxn &＃61; 200010;
7 const int inf &＃61; 1000000007;
8 struct shiki {
9 int net, y;
10 }e[maxn <<1];
11 int lin[maxn], len &＃61; 0;
12 int dfn[maxn], low[maxn];
13 int num &＃61; 0, cnt &＃61; 0, top &＃61; 0;
14 int c_num[maxn], s[maxn];
15 bool in_s[maxn];
16 int sum[maxn];
17 int n, t, ans;
18
19 inline int read() {
20 int x &＃61; 0, y &＃61; 1;
21 char ch &＃61; getchar();
22 while(!isdigit(ch)) {
23 if(ch &＃61;&＃61; &＃39;-&＃39;) y &＃61; 1;
24 ch &＃61; getchar();
25 }
26 while(isdigit(ch)) {
27 x &＃61; (x <<1) &＃43; (x <<3) &＃43; ch - &＃39;0&＃39;;
28 ch &＃61; getchar();
29 }
30 return x * y;
31 }
32
33 inline void insert(int xx, int yy) {
34 e[&＃43;&＃43;len].y &＃61; yy;
35 e[len].net &＃61; lin[xx];
36 lin[xx] &＃61; len;
37 }
38
39 void tarjan(int x) {
40 dfn[x] &＃61; low[x] &＃61; &＃43;&＃43;num;
41 s[&＃43;&＃43;top] &＃61; x, in_s[x] &＃61; 1;
42 for(int i &＃61; lin[x]; i; i &＃61; e[i].net) {
43 int to &＃61; e[i].y;
44 if(!dfn[to]) {
45 tarjan(to);
46 low[x] &＃61; min(low[x], low[to]);
47
48 }
49 else if(in_s[to]) low[x] &＃61; min(low[x], dfn[to]);
50 }
51 if(dfn[x] &＃61;&＃61; low[x]) {
52 cnt&＃43;&＃43;; int k;
53 do {
54 k &＃61; s[top--], in_s[k] &＃61; 0;
55 c_num[k] &＃61; cnt;
56 }while(x !&＃61; k);
57 }
58 }
59
60 int main() {
61 memset(sum, 0, sizeof(sum));
62 n &＃61; read();
63 for(register int i &＃61; 1; i <&＃61; n; &＃43;&＃43;i) {
64 t &＃61; read();
65 insert(i, t);
66 }
67 for(register int i &＃61; 1; i <&＃61; n; &＃43;&＃43;i)
68 if(!dfn[i]) tarjan(i);
69 for(register int i &＃61; 1; i <&＃61; n; &＃43;&＃43;i)
70 sum[c_num[i]]&＃43;&＃43;;
71 ans &＃61; inf;
72 for(register int i &＃61; 1; i <&＃61; cnt; &＃43;&＃43;i)
73 if(sum[i] !&＃61; 1) ans &＃61; min(ans, sum[i]);
74 printf("%d\n", (ans !&＃61; inf) ? ans : 1);
75 return 0;
76 }
T3斗地主
这题当年显然恶心的不少的人
这题确实比较恶心&＃xff0c;尤其是那诡异的一堆牌的出法&＃xff0c;因为和真实斗地主不一样&＃xff0c;比较不适
对于这点&＃xff0c;我们本着&＃xff1a;“所有题面没说是不合法的情况&＃xff0c;都是合法的” 的原则&＃xff0c;可以知道最烦人的大小王&＃xff0c;他们不是对&＃xff0c;他们是单牌&＃xff0c;所以炸弹带大小王是合法的&＃xff01;
因为炸弹可以带两张单牌。
我们贪心的想一想&＃xff0c;显然我们要想出牌次数最小&＃xff0c;一定是要尽可能的先把所有能一次丢走顺子和带牌都出完&＃xff0c;最后剩下的牌在甩完就好&＃xff0c;所以我们可以爆搜顺子和带牌加上最后剩下的牌的出牌次数&＃xff0c;答案求min
好吧和贪心并没有什么关系&＃xff0c;我们做这题首先要有一个合理的搜索顺序&＃xff1a;先搜顺子和带牌&＃xff0c;最后处理剩余的牌
因为显然&＃xff0c;除了顺子&＃xff0c;带牌&＃xff0c;剩下的无论是什么都可以一次出完&＃xff0c;而相比枚举出掉什么单牌或对子或炸弹
显然顺子和带牌的情况更方便处理&＃xff0c;这样我们就可以爆搜了&＃xff0c;奥对&＃xff0c;顺子和带牌先搜哪个后搜哪个都是可以A题的
1 #include
2 using namespace std;
3 const int maxn &＃61; 25;
4 const int inf &＃61; 1000000007;
5 int sum[maxn];
6 int T, n, ans;
7
8 inline int read() {
9 int x &＃61; 0, y &＃61; 1;
10 char ch &＃61; getchar();
11 while(!isdigit(ch)) {
12 if(ch &＃61;&＃61; &＃39;-&＃39;) y &＃61; -1;
13 ch &＃61; getchar();
14 }
15 while(isdigit(ch)) {
16 x &＃61; (x <<1) &＃43; (x <<3) &＃43; ch - &＃39;0&＃39;;
17 ch &＃61; getchar();
18 }
19 return x * y;
20 }
21
22 void dfs_kill(int x) {//出牌次数
23 /*
24 可以公开的情报&＃xff1a;
25 出牌方式有火箭&＃xff0c;炸弹&＃xff0c;单牌&＃xff0c;对牌&＃xff0c;三不带&＃xff0c;三带单&＃xff0c;三带对&＃xff0c;
26 顺子&＃xff0c;连对&＃xff0c;三顺, 四带二(且带的两张牌不要求相同&＃xff09;
27 */
28 if(x >&＃61; ans) return;
29 //顺子势力
30 int op &＃61; 0;//单顺
31 for(register int i &＃61; 3; i <&＃61; 14; &＃43;&＃43;i) {//2与双王不可用
32 if(sum[i] <1) op &＃61; 0;//打断顺子
33 else {
34 op&＃43;&＃43;;//长度加1
35 if(op >&＃61; 5) {
36 for(register int j &＃61; i - op &＃43; 1; j <&＃61; i; &＃43;&＃43;j) sum[j]--;//出牌
37 dfs_kill(x &＃43; 1);
38 for(register int j &＃61; i - op &＃43; 1; j <&＃61; i; &＃43;&＃43;j) sum[j]&＃43;&＃43;;//回溯
39 }
40 }
41 }
42 op &＃61; 0;//连对
43 for(register int i &＃61; 3; i <&＃61; 14; &＃43;&＃43;i) {
44 if(sum[i] <2) op &＃61; 0;//打断连对
45 else {
46 op&＃43;&＃43;;
47 if(op >&＃61; 3) {
48 for(register int j &＃61; i - op &＃43; 1; j <&＃61; i; &＃43;&＃43;j) sum[j] -&＃61; 2;
49 dfs_kill(x &＃43; 1);
50 for(register int j &＃61; i - op &＃43; 1; j <&＃61; i; &＃43;&＃43;j) sum[j] &＃43;&＃61; 2;
51 }
52 }
53 }
54 op &＃61; 0;//三顺
55 for(register int i &＃61; 3; i <&＃61; 14; &＃43;&＃43;i) {
56 if(sum[i] <3) op &＃61; 0;
57 else {
58 op&＃43;&＃43;;
59 if(op >&＃61; 2) {
60 for(register int j &＃61; i - op &＃43; 1; j <&＃61; i; &＃43;&＃43;j) sum[j] -&＃61; 3;
61 dfs_kill(x &＃43; 1);
62 for(register int j &＃61; i - op &＃43; 1; j <&＃61; i; &＃43;&＃43;j) sum[j] &＃43;&＃61; 3;
63 }
64 }
65 }
66 //带牌
67 for(register int i &＃61; 2; i <&＃61; 14; &＃43;&＃43;i) {//大小王不能带牌
68 if(sum[i] <3) continue;//连三带都不行的
69 sum[i] -&＃61; 3;//大家都先搞三带
70 for(register int j &＃61; 2; j <&＃61; 16; &＃43;&＃43;j) {//三带一居然能带大小王??
71 if(sum[j] <1 || j &＃61;&＃61; i) continue;
72 sum[j]--;
73 dfs_kill(x &＃43; 1);
74 sum[j]&＃43;&＃43;;
75 }
76 for(register int j &＃61; 2; j <&＃61; 14; &＃43;&＃43;j) {//三带二&＃xff0c;大小王不算对子
77 if(sum[j] <2 || j &＃61;&＃61; i) continue;
78 sum[j] -&＃61; 2;
79 dfs_kill(x &＃43; 1);
80 sum[j] &＃43;&＃61; 2;
81 }
82 sum[i] &＃43;&＃61; 3;
83 if(sum[i] > 3) {//一些群众可以四带
84 sum[i] -&＃61; 4;
85 for(register int j &＃61; 2; j <&＃61; 15; &＃43;&＃43;j) {//带单牌之时,大小王算单牌
86 if(sum[j] <1 || j &＃61;&＃61; i) continue;
87 sum[j]--;
88 for(register int k &＃61; 2; k <&＃61; 15; &＃43;&＃43;k) {
89 if(sum[k] <1 || (k &＃61;&＃61; j && k !&＃61; 15) || k &＃61;&＃61; i) continue;
90 sum[k]--;
91 dfs_kill(x &＃43; 1);
92 sum[k]&＃43;&＃43;;
93 }
94 sum[j]&＃43;&＃43;;
95 }
96 for(register int j &＃61; 2; j <&＃61; 14; &＃43;&＃43;j) {//带双牌之时,大小王不算对子
97 if(sum[j] <2 || j &＃61;&＃61; i) continue;
98 sum[j] -&＃61; 2;
99 for(register int k &＃61; 2; k <&＃61; 14; &＃43;&＃43;k) {
100 if(sum[k] <2 || k &＃61;&＃61; j || k &＃61;&＃61; i) continue;
101 sum[k] -&＃61; 2;
102 dfs_kill(x &＃43; 1);
103 sum[k] &＃43;&＃61; 2;
104 }
105 sum[j] &＃43;&＃61; 2;
106 }
107 sum[i] &＃43;&＃61; 4;
108 }
109 }
110 //已经处理完了顺子&＃xff0c;连对&＃xff0c;三顺&＃xff0c;三带一&＃xff0c;三带二&＃xff0c;四带二单&＃xff0c;四带二对
111 //对于剩下的势力&＃xff0c;显然可以一次性丢出去
112 for(register int i &＃61; 2; i <&＃61; 15; &＃43;&＃43;i) if(sum[i]) x&＃43;&＃43;;
113 ans &＃61; min(ans, x);
114 }
115
116 int main() {
117 // freopen("landlords.in", "r", stdin);
118 // freopen("landlords.out", "w", stdout);
119 T &＃61; read(), n &＃61; read();
120 while(T--) {
121 memset(sum, 0, sizeof(sum));
122 ans &＃61; inf;
123 for(register int i &＃61; 1; i <&＃61; n; &＃43;&＃43;i) {
124 int which &＃61; read(), col &＃61; read();
125 if(which &＃61;&＃61; 0) sum[15]&＃43;&＃43;;//大小王放在同一个位置
126 else if(which &＃61;&＃61; 1) sum[14]&＃43;&＃43;;//塞进一个A&＃xff0c;因为A可以丢进顺子等组合且比较大&＃xff0c;放在后面
127 else sum[which]&＃43;&＃43;;
128 }
129 dfs_kill(0);
130 printf("%d\n", ans);
131 }
132 return 0;
133 }
这样我们就把Noip2015给AK了&＃xff0c;实际上就这套题的难度来看&＃xff0c;前两题简直是送分&＃xff0c;我写前两题甚至没超过半个小时&＃xff08;大概&＃xff1f;&＃xff09;
最后T3确定好规则和搜索顺序&＃xff0c;因为数据随机&＃xff0c;所以直接爆搜并不难过。这样&＃xff0c;你就有个极大的优势了
Day2
跳石头
挺经典的二分答案题目&＃xff08;不&＃xff09;
二分一个距离&＃xff0c;然后开始判定是否合法&＃xff1a;
定义一个变量now表示现在在哪块石头上&＃xff0c;ans表示能拿掉的石头数量
若枚举到的石头i与now的距离小于二分出的距离&＃xff0c;将ans&＃43;&＃43;;
否则令now &＃61; i;
若最后ans <&＃61; m&＃xff0c;则距离不够&＃xff08;显然会有人想知道为什么ans&＃61;&＃61;m不行&＃xff0c;我们想一下&＃xff0c;我们能够跳到一块石头为i&＃43;m&＃xff0c;那么按照我们的判定方式&＃xff0c;就将i&＃43;m拿掉了&＃xff0c;然而我们能不能跳到第i&＃43;m&＃43;1块石头呢&＃xff1f;因为必然要有一块岩石做终点&＃xff0c;不能跳到水里&＃xff0c;所以我们至少要能够拿掉m&＃43;1块石头才能说明我们一定能拿掉m块石头并且保证有起点和终点&＃xff09;
1 #include
2 using namespace std;
3 const int maxn &＃61; 50010;
4 int a[maxn];
5 int L, m, n;
6
7 inline int read() {
8 int x &＃61; 0, y &＃61; 1;
9 char ch &＃61; getchar();
10 while(!isdigit(ch)) {
11 if(ch &＃61;&＃61; &＃39;-&＃39;) y &＃61; -1;
12 ch &＃61; getchar();
13 }
14 while(isdigit(ch)) {
15 x &＃61; (x <<1) &＃43; (x <<3) &＃43; ch - &＃39;0&＃39;;
16 ch &＃61; getchar();
17 }
18 return x * y;
19 }
20
21 inline bool check(int x) {
22 int ans &＃61; 0, now &＃61; 0;
23 for(int i &＃61; 1; i <&＃61; n; &＃43;&＃43;i)
24 if(a[i] - now
25 else now &＃61; a[i];
26 return ans <&＃61; m;
27 }
28
29 int main() {
30 L &＃61; read(), n &＃61; read(), m &＃61; read();
31 for(int i &＃61; 1; i <&＃61; n; &＃43;&＃43;i) a[i] &＃61; read();
32 int l &＃61; 0, r &＃61; L;
33 while(l < r) {
34 int mid &＃61; l &＃43; r >> 1;
35 if(check(mid)) l &＃61; mid &＃43; 1;
36 else r &＃61; mid - 1;
37 }
38 if(!check(l)) l -&＃61; 1;
39 printf("%d\n", l);
40 return 0;
41 }
子串
这题&＃xff0c;还挺好写的....
高端做法不会&＃xff0c;但是我们可以很容易的想到一个四维的状态
f[i, j, k, 0/1]表示A串取到了第i个字符&＃xff0c;B串匹配了j个字符&＃xff0c;使用了k个子串&＃xff0c;第i个字符取或是不取
方程&＃xff1a;
f[i][j][k][0] &＃61; (f[i-1][j][k][0] &＃43; f[i-1][j][k][1]) % mod
如果ai !&＃61; bj 则 f[i][j][k][1] &＃61; 0
否则 f[i][j][k][1] &＃61; (f[i-1][j - 1][k][1] &＃43; (f[i-1][j - 1][k - 1][0] &＃43; f[i-1][j - 1][k - 1][1]
因为空间问题&＃xff08;毕竟是四维嘛...&＃xff09;我们使用滚动数组即可
初态&＃xff1a;f[0][0][0][0] &＃61; f[1][0][0][0] &＃61; 1
末态&＃xff1a;f[n][m][k][0]&＃43;f[n][m][k][1]
然后就简简单单地A题了
1 #include
2 using namespace std;
3 const int mod &＃61; 1000000007;
4 const int maxn &＃61; 1010;
5 const int maxm &＃61; 210;
6 int f[2][maxm][maxm][2];
7 char a[maxn], b[maxm];
8 int n, m, l, id &＃61; 1;
9
10 inline int read() {
11 int x &＃61; 0, y &＃61; 1;
12 char ch &＃61; getchar();
13 while(!isdigit(ch)) {
14 if(ch &＃61;&＃61; &＃39;-&＃39;) y &＃61; -1;
15 ch &＃61; getchar();
16 }
17 while(isdigit(ch)) {
18 x &＃61; (x <<1) &＃43; (x <<3) &＃43; ch - &＃39;0&＃39;;
19 ch &＃61; getchar();
20 }
21 return x * y;
22 }
23
24 int main() {
25 // freopen("a.in", "r", stdin);
26 // freopen("a.out", "w", stdout);
27 n &＃61; read(), m &＃61; read(), l &＃61; read();
28 scanf("%s%s", a &＃43; 1, b &＃43; 1);
29 f[0][0][0][0] &＃61; f[1][0][0][0] &＃61; 1;
30 for(register int i &＃61; 1; i <&＃61; n; &＃43;&＃43;i) {
31 for(register int j &＃61; 1; j <&＃61; m; &＃43;&＃43;j)
32 for(register int k &＃61; 1; k <&＃61; l; &＃43;&＃43;k) {
33 f[i&1][j][k][0] &＃61; (f[(i-1)&1][j][k][0] &＃43; f[(i-1)&1][j][k][1]) % mod;
34 if(a[i] !&＃61; b[j]) f[i&1][j][k][1] &＃61; 0;
35 else f[i&1][j][k][1] &＃61; (f[(i-1)&1][j - 1][k][1] &＃43; (f[(i-1)&1][j - 1][k - 1][0] &＃43; f[(i-1)&1][j - 1][k - 1][1]) % mod) % mod;
36 }
37 }
38 printf("%d\n", (f[n & 1][m][l][0] &＃43; f[n & 1][m][l][1]) % mod);
39 return 0;
40 }
运输计划
两天来最难的题&＃xff0c;当然对于一些大佬&＃xff0c;这题比斗地主简单
题解&＃xff1a;LCA&＃43;差分&＃43;二分
先咕咕咕一下回头一定补咕咕咕咕
京公网安备 11010802041100号