999网站免费,网赌怎么推广拉客户,找人做公司网站,济南公司网站开发cf的比赛越来越有难度了……至少我做起来是这样。 先看看题目吧#xff1a;点我。 这次比赛是北京时间21:35开始的#xff0c;算是比较良心。 【A】奇数与结束 奇数从哪里开始#xff0c;又在哪里结束#xff1f;梦想从何处起航#xff0c;它们又是否会破灭呢#… cf的比赛越来越有难度了……至少我做起来是这样。 先看看题目吧点我。 这次比赛是北京时间21:35开始的算是比较良心。 【A】奇数与结束 奇数从哪里开始又在哪里结束梦想从何处起航它们又是否会破灭呢 给定一个长度为n的序列。确定能不能将序列分成奇数个长度为奇数的非空字串而且这其中每个子串以奇数开头以奇数结尾。可以只分成一个1也是奇数。 输入 第一行一个正整数n表示序列长度。 第二行n个整数表示序列中的元素。 输出 输出Yes或No来表示能否做到把序列按要求分割。 样例输入1 51 0 1 5 1 样例输出1 Yes 样例输入2 43 9 9 3 样例输出2 No 题解 当时想了一个n²的DP之后发现实在是太naive。 讲一下DP思路吧用f1[i]表示能否将a[1...i]分割成奇数个奇数长度的子串并且每个子串以奇数开头结尾f2[i]表示能否分割成偶数个子串。 于是f1[i]OR(f2[j] (a[j1...i]长度为奇数并且以奇数开头结尾) )f2[i]OR(f1[j] (a[j1...i]长度为奇数并且以奇数开头结尾) ). 特别的f1[0]falsef2[0]true。 这种做法就可以过了但是有更优秀的做法 把序列分成奇数个奇数长度的序列那么这个序列也是奇数长度的。偶数长度的直接No。 再考虑把序列分成两个以上的序列那么最开始的序列的起始元素必须是奇数最末尾的序列的结尾元素也必须是奇数。 这就对应了原序列的第一个与最后一个元素必须是奇数而这时我们只分一段就好了。 就是说我们只需要判断n的奇偶a[1]的奇偶和a[n]的奇偶就可以了。 程序 1 #include cstdio2 static const int MAXN 102;3 4 int n;5 int a[MAXN];6 7 int main()8 {9 scanf(%d, n);
10 for (int i 0; i n; i) scanf(%d, a[i]);
11
12 puts((n 1) (a[0] 1) (a[n - 1] 1) ? Yes : No);
13 return 0;
14 } 【B】 目前没做出来调出来了再说自己的做法吧 先贴标程 1 #include bits/stdc.h2 #define eps 1e-73 using namespace std;4 int read()5 {6 int x0,f1;char chgetchar();7 while (ch0||ch9){if (ch-) f-1;chgetchar();}8 while (ch0ch9){xx*10ch-0;chgetchar();}9 return x*f;
10 }
11 int n,a[1007];
12 bool vis[1007];
13 bool check(double k,int b)
14 {
15 memset(vis,false,sizeof(vis));
16 int cnt0;
17 for (int i1;in;i)
18 {
19 if (a[i]-b1LL*k*(i-1))
20 {
21 vis[i]true;
22 cnt;
23 }
24 }
25 if (cntn) return false;
26 if (cntn-1) return true;
27 int pos10;
28 for (int i1;in;i)
29 if (!vis[i]pos10) pos1i;
30 for (int ipos11;in;i)
31 if (!vis[i])
32 {
33 if (fabs((double)(a[i]-a[pos1])/(i-pos1)-k)eps) return false;
34 }
35 return true;
36 }
37 int main()
38 {
39 nread();
40 for (int i1;in;i)
41 a[i]read();
42 bool ansfalse;
43 ans|check(1.0*(a[2]-a[1]),a[1]);
44 ans|check(0.5*(a[3]-a[1]),a[1]);
45 ans|check(1.0*(a[3]-a[2]),a[2]*2-a[3]);
46 if (ans) printf(Yes\n); else printf(No\n);
47 return 0;
48 } 【C】 题目都没看懂真的很难受这题挺难的。 标程 1 #include bits/stdc.h2 3 using namespace std;4 5 using ll long long;6 using ld long double;7 using D double;8 using uint unsigned int;9 templatetypename T
10 using pair2 pairT, T;
11
12 #ifdef WIN32
13 #define LLD %I64d
14 #else
15 #define LLD %lld
16 #endif
17
18 #define pb push_back
19 #define mp make_pair
20 #define all(x) (x).begin(),(x).end()
21 #define fi first
22 #define se second
23
24 int main()
25 {
26 int k;
27 scanf(%d, k);
28 for (int i 0; i 26; i)
29 {
30 int cnt 1;
31 while ((cnt 1) * cnt / 2 k) cnt;
32 k - cnt * (cnt - 1) / 2;
33 for (int j 0; j cnt; j) printf(%c, a i);
34 }
35 return 0;
36 } 【D】Rooters Song 无论目标何在无论遇见何人让我们一同将这首歌传唱。 在平面直角坐标系中有一个长方形舞台四角分别是(0,0)(0,h)(w,0)(w,h)。 可以看出在有任何人进入舞台之前不会有任何碰撞发生。 在舞台的左边界和下边界站着一些舞者。分成两组 ①竖直站在(xi,0)上沿着y正方向前进向上。 ②水平站在(0,yi)上沿着x正方向前进向右。 按照编舞指导第i个舞者需要在前ti毫秒内站着不动然后沿着指定方向以1单位/毫秒的速度前进直到碰到舞台的边界为止。 当两个舞者碰撞时她们会立刻改变各自的前进方向然后继续沿着新的方向前进。 舞者们只要碰到了舞台的边界就会停止请求出每个舞者最终停下的位置。 输入 第一行有三个数n,w,h。表示舞者数量舞台的长宽。 接下来n行每行三个数gi,pi,ti表示第i个舞者所在的组gi1竖直组gi2水平组坐标位置gi1则pixigi2则piyi以及等待时间。 保证0xiw0yih。并保证没有两个舞者既在相同的组还有相同的位置和等待时间。 输出 n行每行两个数xi,yi。表示第i个舞者最终停在哪里。 样例输入1 8 10 81 1 101 4 131 7 11 8 22 2 02 5 142 6 02 6 1 样例输出1 4 810 58 810 610 21 87 810 6 样例输入2 3 2 31 1 22 1 11 1 5 样例输出2 1 32 11 3 数据范围及提示 1n1000002w,h1000001gi21pi999990ti100000。 对于样例数据1这是对应的图 对于样例数据2没有舞者碰撞。 题解 很难的一题不过我看来比C题简单…… 注意到每个舞者出发后每毫秒其坐标总是有一个加一故(xiyi)总是在增加。 而且我们发现只有(xiyi)相同的舞者才会碰撞。我们把(xiyi)的值相同的舞者分在一起处理。 如何确定(xiyi)的值呢可以发现对于每个舞者可以把(pi-ti)近似看做(xiyi)(pi-ti)相同的舞者可能碰撞而(pi-ti)不同的不可能碰撞。 我们对舞者按照(pi-ti)排序处理出(pi-ti)相同的舞者。 对于(pi-ti)相同的舞者我们如何处理呢 试着把舞台斜过来看吧让(0,0)在最下方(w,h)在最顶端(0,h)在左侧(w,0)在最右侧。 这样对于那些(pi-ti)相同的舞者即出发后(xiyi)相同的舞者们她们在同一时间点必然处在同一水平线上。 并且每过一毫秒她们向上走√2/2单位向左或向右走√2/2单位。 这时候的碰撞要如何处理呢 注意到在没有碰撞发生前舞者从左到右的顺序是先是水平方向的舞者坐标从大到小下来然后是竖直方向的舞者坐标从小到大往右走。 而所有碰撞都发生了之后呢舞者的相对位置是不会改变的原本在最左侧的舞者仍然在左侧。舞者位置不会交换。 或者……这是另一种形式的交换了呢注意到在水平方向坐标最大的舞者没有去到她本来应该去的位置而是去了竖直方向第一个舞者应该去的位置。 是的她们的位置交换了但是这种交换很有规律把舞者分成水平方向和竖直方向那么水平方向的舞者按顺序要去到竖直方向的舞者按顺序应该去到的位置。依次推下来就可以确定舞者最终的位置。我不太好解释这种方法的具体实现先贴代码吧。 排序时要注意第一关键字是(pi-ti)第二关键字是先水平后竖直第三关键字是初始坐标水平的从大到小竖直的从小到大。 复杂度O(nlogn) 1 #includecstdio2 #includealgorithm3 #includecstring4 #define F(i,a,b) for(int ia;ib;i)5 #define F2(i,a,b) for(int ia;ib;i)6 int n,w,h,g[100002],p[100002],t[100002],I[100002],Ans[100002],Ansg[100002];7 inline bool cmp(int x,int y){8 if(p[x]-t[x]p[y]-t[y]) return 1;9 else if(p[x]-t[x]p[y]-t[y]) return 0;
10 else{
11 if(g[x]g[y]) return 1;
12 else if(g[x]g[y]) return 0;
13 else{
14 if(g[x]1) return p[x]p[y];
15 else return p[x]p[y];
16 }
17 }
18 }
19 int main(){
20 scanf(%d%d%d,n,w,h);
21 F(i,1,n) scanf(%d%d%d,gi,pi,ti),I[i]i;
22 std::sort(I1,In1,cmp);
23 I[n1]0; p[0]99999999; t[0]-99999999;
24 int hor0,ver0;
25 F(i,1,n){
26 if(g[I[i]]1) ver; else hor;
27 if(p[I[i]]-t[I[i]]!p[I[i1]]-t[I[i1]]){
28 int ji-hor-ver1, ki-ver1,l,o;
29 for(lk,oj;li;l,o)
30 Ans[I[o]]p[I[l]],Ansg[I[o]]g[I[l]];
31 for(;oi;o,j)
32 Ans[I[o]]p[I[j]],Ansg[I[o]]g[I[j]];
33 verhor0;
34 }
35 }
36 F(i,1,n) if(Ansg[i]1) printf(%d %d\n,Ans[i],h); else printf(%d %d\n,w,Ans[i]);
37 return 0;
38 } 【E】 没看题以后再补吧。 转载于:https://www.cnblogs.com/PinkRabbit/p/7466204.html
