這個(gè)比賽感覺超級(jí)差，評(píng)測(cè)機(jī)前兩個(gè)小時(shí)根本沒用，所有題目都是in queue ，所以那個(gè)時(shí)候就沒什么興趣了，但是后面好了的情況下，又做了幾題

首先是A題Fast Fourier Transform ，簽到題

題意大致是給你兩個(gè)數(shù)的和以及這兩個(gè)數(shù)的最大公約數(shù)，讓你求這兩個(gè)數(shù)，如果不存在就輸出-1

那先假定一個(gè)數(shù)是這個(gè)最大公約數(shù)，另一個(gè)數(shù)這個(gè)和減去最大公約數(shù)，最后判斷是否滿足這兩個(gè)數(shù)的最大公約數(shù)

#include <cstdio> #include <iostream> #include <string> #include <cstring> using namespace std; int main(){int n,m;cin>>n>>m;if(n%m!=0||n==m) cout<<-1<<endl;else {cout<<m<<' '<<n-m<<endl;}return 0; }

B題Suffix Automaton，數(shù)學(xué)題

給一個(gè)凸多邊形，問這個(gè)凸多邊形的頂點(diǎn)所能構(gòu)成的三角形中的最小面積乘以2.

就是遍歷這個(gè)凸多邊形的頂點(diǎn)，如果要最小面積，這三個(gè)頂點(diǎn)一定是在凸多邊形中連續(xù)的，然后求三角形面積就用在坐標(biāo)軸上的向量求面積也就是交叉相乘相減再除以2，但是要求的是最小面積的兩倍，所以也就不必除以2了。

#include <cstdio> #include <iostream> #include <string> #include <algorithm> #include <cstring> #include <cmath> using namespace std; struct node{long long x,y; }s[200005];unsigned long long area(node a,node b,node c){unsigned long long sum=abs(a.x*b.y+b.x*c.y+c.x*a.y-a.x*c.y-b.x*a.y-c.x*b.y);return sum;} int main() {int n,m;cin>>n;for(int i=0;i<n;i++) cin>>s[i].x>>s[i].y;unsigned long long minx=1e19;for(int i=0;i<n-2;i++) minx=min(minx,area(s[i],s[i+1],s[i+2]));minx=min(minx,area(s[0],s[n-1],s[n-2]));minx=min(minx,area(s[0],s[1],s[n-1]));cout<<minx<<endl; }

C題Size Balanced Tree，區(qū)間貪心

給你n個(gè)區(qū)間，要求選取最少的點(diǎn)，滿足每個(gè)區(qū)間上至少有一個(gè)點(diǎn)

思路：就是將區(qū)間按終點(diǎn)排序，然后從小到大遍歷一遍，每次先確定第一個(gè)終點(diǎn)的位置，如果小于下一個(gè)的起點(diǎn)小于這個(gè)終點(diǎn)則跳過，否則就記錄下這個(gè)終點(diǎn)，并標(biāo)記這個(gè)超過終點(diǎn)的位置的終點(diǎn)

#include <cstdio> #include <iostream> #include <string> #include <algorithm> #include <cstring> using namespace std; struct node{int a,b; }s[200005];int cmp(node x,node y){if(x.b==y.b) return x.a<y.a;return x.b<y.b;} int main() {int n,m=0;int t=0;int cnt[200005];cin>>n;for(int i=0;i<n;i++) cin>>s[i].a>>s[i].b;sort(s,s+n,cmp);int sw=s[0].b;for(int i=1;i<n;i++){if(s[i].a>sw){cnt[t++]=sw;sw=s[i].b;}}cnt[t++]=sw;cout<<t<<endl;cout<<cnt[0];for(int i=1;i<t;i++) cout<<' '<<cnt[i]; }

E題Recurrent Neural Network，字符串操作

首先先給你兩個(gè)字符串a(chǎn)，b，給你一個(gè)機(jī)會(huì)操作字符串，即顛倒a字符串中任意子串僅一次，問是否能將兩個(gè)字符串變成相同

思路：我的思路可能跟大佬的思路不太一樣，也比較復(fù)雜，就是先找到兩個(gè)字符串第一個(gè)不同的位置，然后標(biāo)記一下，繼續(xù)在b串中找相同字符的位置并存起來(lái)，只需要遍歷a串中的這個(gè)位置和存起來(lái)的所有位置的顛倒情況

是否存在使得兩串相等的情況就OK了。

大佬的思路就是從前向后找第一個(gè)不同的位置，標(biāo)記，然后從后向前找第一個(gè)不同的位置，標(biāo)記，然后只需要顛倒這兩個(gè)位置的子串再判斷就行了

#include <cstdio> #include <iostream> #include <string> #include <cstring> using namespace std; int main(){string a,b;string c;int vis[200005];int n=0,m=-1;cin>>a>>b;memset(vis,0,sizeof(vis));for(int i=0;i<a.length();i++){if(a[i]!=b[i]){m=i;for(int j=i+1;j<a.length();j++){if(a[i]==b[j]) vis[n++]=j;}break;}}if(m==-1){cout<<"YES"<<endl;return 0;}for(int i=0;i<n;i++){c=a;int sw=1;int ss=(m+vis[i])/2;if((m+vis[i])%2==0) sw=0;for(int j=ss;j>=m;j--){swap(c[j],c[ss+(sw++)]);}if(c==b){cout<<"YES"<<endl;return 0;}}cout<<"NO"<<endl;return 0; }

J題簽到題，隊(duì)友a(bǔ)的，還拿了1血。。

給你n個(gè)邊，問能找到的最大平行四邊形數(shù)是多少

平行四邊形只要兩兩相等就OK了，那只需要找每個(gè)長(zhǎng)度有多少個(gè)相同的就OK了，數(shù)據(jù)較小可以用數(shù)組存

Select Code #include <iostream> #include<stdio.h> #include<string.h> #include<math.h> #include<algorithm> #include<queue> using namespace std; int a[200005]; int main() {int n,i,x;cin>>n;while(n--){cin>>x;a[x]++;}int sum=0;for(i=1;i<=200001;i++){if(a[i]){sum+=a[i]/2;}}cout<<sum/2<<endl;return 0; }

?

轉(zhuǎn)載于:https://www.cnblogs.com/maybe96/p/9466371.html

總結(jié)

以上是生活随笔為你收集整理的SICNU 2018 Summer Training #9的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。