SUST_2018 焦作站亞洲區(qū)域賽校內(nèi)選拔賽

A、高速????????by yoyo

tag：圖論、最短路

//最短路 #include<bits/stdc++.h> using namespace std; typedef long long ll; const int maxx = 0x3f3f3f3f; const int maxn = 1e5+7; int t,n,m,cnt; int dis[maxn]; //當(dāng)前該點(diǎn)到原點(diǎn)最短距離 bool vis[maxn]; //是否訪問(wèn)過(guò) int head[maxn]; //點(diǎn)集 struct EDGE{int next,to,w,l,r; //上一條邊，下一個(gè)點(diǎn)，權(quán)值，左值，右值 }edge[2*maxn]; //邊集 struct NODE{int u,dis;NODE(){}NODE(int u,ll w):u(u),dis(w){}bool operator <(const NODE &a)const{return dis>a.dis;} }node[2*maxn]; //點(diǎn)集加最短距離 void add(int u, int v, int w, int l,int r){ //構(gòu)建邊集edge[cnt].next = head[u];edge[cnt].to = v;edge[cnt].w = w;edge[cnt].l = l;edge[cnt].r = r;head[u] = cnt;cnt++; } void init(){ //初始化cnt = 0;memset(head,-1,sizeof(head));memset(dis,maxx,sizeof(dis));memset(vis,false,sizeof(vis)); } void read(){ //讀入數(shù)據(jù)int u,v,w,l,r;scanf("%d%d",&n,&m);for(int i = 0;i < m; i++){scanf("%d%d%d%d%d",&u,&v,&w,&l,&r);add(u,v,w,l,r);add(v,u,w,l,r);} } void init_data(int kk){ //初始化數(shù)據(jù)vis[kk] = false;dis[kk] = maxx; } int solve(int s){priority_queue<NODE>q; //儲(chǔ)存最短距離q.push(NODE(s,0)); //讀入原點(diǎn)while(!q.empty()){ //隊(duì)列為空則無(wú)法到達(dá)int kk = q.top().u; //儲(chǔ)存當(dāng)前最短距離下標(biāo)int minD = q.top().dis; //儲(chǔ)存當(dāng)前最短距離q.pop();if(kk==n) //若下標(biāo)為目標(biāo)值，returnreturn minD;vis[kk] = true; //該點(diǎn)是否訪問(wèn)for(int l = head[kk]; l!=-1; l=edge[l].next){ //松弛邊if(!vis[edge[l].to]&&minD<=edge[l].r&&minD>=edge[l].l&&minD + edge[l].w < dis[edge[l].to]){dis[edge[l].to] = minD + edge[l].w;q.push(NODE(edge[l].to,dis[edge[l].to])); //將松弛后的邊壓入隊(duì)列}}init_data(kk); //初始化數(shù)據(jù)}return 0; } int main(){scanf("%d",&t);while(t--){init(); //初始化read(); //讀入printf("%d\n",solve(1)); //解決方案}return 0; }

B、Outlook????????by 紫芝

tag：計(jì)算幾何、最短路

本題可以看出是計(jì)算幾何 + 最短路問(wèn)題，最重要的只是對(duì)圖進(jìn)行建模。
所以我們考慮在圖上摳出特殊點(diǎn)，來(lái)跑最短路。
特殊點(diǎn)包括墻的兩端之類的。

#include<cstring> #include<algorithm> #include<cmath> #include<cstdio> #include<vector> #include<queue> #define N 1010 #define inf 999999999.0 using namespace std;struct data {double x;double y[4]; }dt[10]; bool cmpx(data a,data b) {return a.x<b.x; } struct point{double x,y;int id; }; struct line{point d,u;int th; }; int n,pnum,pline; vector<line> vec; vector<point> p; double mp[N][N]; void add_line(point a,point b) {line it;it.d=a;it.u=b;it.th=pline++;vec.push_back(it); } //叉積 double multi(point p0,point p1,point p2) {return (p1.x-p0.x)*(p2.y-p0.y)-(p1.y-p0.y)*(p2.x-p0.x); } //判斷兩條線段是否相交 bool is_inter(point s1,point e1,point s2,point e2) {return(max(s1.x,e1.x)>=min(s2.x,e2.x))&&(max(s2.x,e2.x)>=min(s1.x,e1.x))&&(max(s1.y,e1.y)>=min(s2.y,e2.y))&&(max(s2.y,e2.y)>=min(s1.y,e1.y))&&(multi(s1,s2,e1)*multi(s1,e1,e2)>0)&&(multi(s2,s1,e2)*multi(s2,e2,e1)>0);} double dist(point a,point b) {return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));} //建圖 void init() {for(int i=0;i<=pnum;i++){for(int j=0;j<=pnum;j++){if(i==j){mp[i][j]=0.0;continue;}bool flag=1;point s1=p[i],e1=p[j];int l=(i+1)/2,r=(j+1)/2;for(int k=l+1;k<r;k++){if(is_inter(s1,e1,vec[k].d,vec[k].u)){flag=0;break;}}if(flag) mp[i][j]=mp[i][j]=dist(s1,e1);else mp[i][j]=mp[i][j]=inf;}}} bool vis[N]; int pre[N]; double d[N]; void Dijkstra(int begin) {for(int i=0;i<=pnum;i++){d[i]=inf;vis[i]=false;}d[begin]=0;for(int j=0;j<=pnum;j++){int k=-1,MIN=inf;for(int i=0;i<=pnum;i++)if(!vis[i]&&d[i]<MIN){MIN=d[i];k=i;}if(k==-1) break;vis[k]=1;for(int i=0;i<=pnum;i++)if(!vis[i]&&d[i]<MIN){MIN=d[i];k=i;}if(k==-1) break;vis[k]=1;for(int i=0;i<=pnum;i++)if(!vis[i]&&d[k]+mp[k][i]<d[i]){d[i]=d[k]+mp[k][i];}} } int main() {//freopen("test.in","r",stdin);//freopen("test.out","w",stdout);while(scanf("%d",&n)!=EOF&&n!=-1){vec.clear();p.clear();double x,y1,y2,y3,y4;pnum=0;pline=0;point a,b;a.x=0,a.y=5.0,a.id=pnum++;p.push_back(a);for(int i=0;i<n;i++){scanf("%lf",&dt[i].x);for(int j=0;j<4;j++)scanf("%lf",&dt[i].y[j]);sort(dt[i].y,dt[i].y+4);}sort(dt,dt+n,cmpx);/*for(int i=0;i<n;i++){printf("%.0lf\n",dt[i].x);for(int j=0;j<4;j++)printf("%.0lf ",dt[i].y[j]);printf("\n");} */for(int i=0;i<n;i++){a.x=dt[i].x;b.x=dt[i].x;a.y=0.0;b.y=dt[i].y[0];a.id=pnum++;b.id=pnum++;add_line(a,b);p.push_back(a);p.push_back(b);a.y=dt[i].y[1];b.y=dt[i].y[2];a.id=pnum++;b.id=pnum++;add_line(a,b);p.push_back(a);p.push_back(b);a.y=dt[i].y[3];b.y=10.0;a.id=pnum++;b.id=pnum++;add_line(a,b);p.push_back(a);p.push_back(b);}a.x=10.0;a.y=5.0;a.id=pnum;p.push_back(a);init();Dijkstra(0);printf("%.2f\n",d[pnum]);}return 0; }

C、千年老二????????by yoyo

tag：圖論、生成樹(shù)

//次小生成樹(shù) #include<bits/stdc++.h> using namespace std; const int L=1e5+7; const int inf=0x3f3f3f3f; const int maxn=1000+7; int father[maxn],n,m,num[maxn],nPos; //父節(jié)點(diǎn)（并查集），點(diǎn)數(shù)，邊數(shù)，最小生成樹(shù)點(diǎn)集，當(dāng)前訪問(wèn)方位 struct node{int s,y,w; }edge[L]; //邊集，左端點(diǎn)，右端點(diǎn)，權(quán)值 void init(){ //初始化并查集for(int i=0;i<=n;i++)father[i]=i; } int root(int x){ //并查集，構(gòu)造父節(jié)點(diǎn)return father[x]==x?x:father[x]=root(father[x]); } void unite(int x,int y){ //并查集，合并兩個(gè)聯(lián)通圖x=root(x);y=root(y);if(x!=y)father[y]=x; } int alike(int x,int y){ //并查集，判斷是否為同一連通圖return root(x)==root(y); } int cmp(node a,node b){ //sort結(jié)構(gòu)體排序return a.w<b.w; } int secondTree(int pos) //次小生成樹(shù) {init(); //初始化int sum=0,cnt=0;for(int i=0;i<m;i++) //對(duì)于刪去邊后的圖進(jìn)行最小生成樹(shù)運(yùn)算{if(cnt==n-1)break;if(i==pos)continue;if(!alike(edge[i].s,edge[i].y)){unite(edge[i].s,edge[i].y);sum+=edge[i].w;cnt++;}}return cnt!=n-1?-1:sum; //判斷刪除邊后是否能構(gòu)成最小生成樹(shù) } int kruskal(){ //最小生成樹(shù)init();sort(edge,edge+m,cmp); //對(duì)邊進(jìn)行權(quán)值排序int sum=0,cnt=0;for(int i=0;i<m;i++) //每次選擇最小且未訪問(wèn)過(guò)的一條邊{if(cnt==n-1)break;if(!alike(edge[i].s,edge[i].y)){unite(edge[i].s,edge[i].y);sum+=edge[i].w;cnt++;num[++nPos]=i;}}return cnt!=n-1?-1:sum; //判斷邊是否大于等于n-1，否則輸出-1 } void read(){ //讀入數(shù)據(jù)scanf("%d%d",&n,&m);for(int i=0;i<m;i++)scanf("%d%d%d",&edge[i].s,&edge[i].y,&edge[i].w); } void solve(){ //解決方案int Min=inf;nPos=0;int mst=kruskal(); //最小生成樹(shù)值if(mst==-1) { //沒(méi)有最小生成樹(shù)即輸出-1printf("-1\n");return;}for(int i=1;i<=nPos;i++){ //對(duì)最小生成樹(shù)的每條邊進(jìn)行遍歷，選擇刪邊后的最小值int secmst=secondTree(num[i]);if(secmst!=-1) //若沒(méi)有次小生成樹(shù)輸出-1Min=min(Min,secmst);}if(Min!=inf&&Min!=mst)printf("%d\n",Min); //輸出結(jié)果elseprintf("-1\n"); } int main(){int t;scanf("%d",&t);while(t--){read(); //讀入數(shù)據(jù)solve(); //解決方案}return 0; }

D、秋雨綿綿????????by 紫芝

tag：高精度、快速乘

但是由于數(shù)據(jù)范圍過(guò)大，我們用普通乘法會(huì)爆精度，因此我們需要用到特殊的乘法 —— 快速乘。
然后直接暴力遞推相乘即可。

#include<bits/stdc++.h> using namespace std; typedef long long ll; ll ksc(ll x,ll y,ll mod) {return (x*y-(ll)((long double)x/mod*y)*mod+mod)%mod; } ll m0,m1,c,M,k; ll a0,a1; int main() {int ca=0;int T;scanf("%d",&T);while(T--){printf("case #%d:\n",++ca);scanf("%lld%lld%lld%lld%lld%lld%lld",&a0,&a1,&m0,&m1,&c,&k,&M);ll ans=ksc(a0,a1,M);ll a2;for(int i=2;i<=k;i++){a2=((ksc(m0,a1,M)+ksc(m1,a0,M))%M+c)%M;ans=ksc(ans,a2,M);a0=a1;a1=a2;}printf("%lld\n",a2);printf("%lld\n",ans);}return 0; }

當(dāng)然也可以使用Java大數(shù)類，但是一般會(huì)超時(shí)

import java.math.BigInteger; import java.util.Scanner; import java.util.*; public class Main {void solve () {Scanner cin = new Scanner(System.in);int T=cin.nextInt();int ca=0;while((T--)!=0) {BigInteger a0,a1,a2,ans,M,tmp;a0=cin.nextBigInteger();a1=cin.nextBigInteger();int m0=cin.nextInt();int m1=cin.nextInt();int c=cin.nextInt();int k=cin.nextInt();M=cin.nextBigInteger();a2=ans=BigInteger.valueOf(1);ans=ans.multiply(a0);ans=ans.mod(M);ans=ans.multiply(a1);ans=ans.mod(M);for(int i=2;i<=k;i++) {a2=a1.multiply(BigInteger.valueOf(m0)).add(a0.multiply(BigInteger.valueOf(m1))).add(BigInteger.valueOf(c));ans=ans.multiply(a2);ans=ans.mod(M);a0=a1.mod(M);a1=a2.mod(M);}System.out.println("case #"+(++ca)+":");System.out.println(a2.mod(M));System.out.println(ans.mod(M));}cin.close();}public static void main (String[] args) {Main work = new Main();work.solve ();} }

E、RMB 游戲????????by 紫芝

tag：簡(jiǎn)單思維題

簡(jiǎn)單題，不解釋。

#include<stdio.h> #include<algorithm> using namespace std; const int N=2505; int a[N]; bool cmp(int x,int y) {return x>y; } int main() {int t;scanf("%d",&t);while(t--){int n,k;scanf("%d%d",&n,&k);for(int i=0;i<n;i++){scanf("%d",&a[i]);}sort(a,a+n,cmp);for(int i=0;i<n;i++){k-=i;if(k<=0){printf("%d\n",a[i]);break;}}}return 0; }

F、給力臺(tái)球廳????????by yoyo

tag：圖論

//網(wǎng)絡(luò)流 #include<bits/stdc++.h> using namespace std; typedef long long ll; const int INF = 0x3f3f3f3f; //無(wú)窮大 const int maxn = 60007; const int maxm = 1000007; int vis[maxn],d[maxn],pre[maxn],a[maxn],m,n; //是否訪問(wèn)，最短路，前置節(jié)點(diǎn)，流量，邊集，點(diǎn)集 char mp[107][107]; //臺(tái)球地圖 struct Edge{int u, v, c, cost, next; }edge[maxm]; //網(wǎng)絡(luò)流邊集int s[maxn], cnt; //每個(gè)點(diǎn)流量void init(){ //初始化cnt = 0;memset(s, -1, sizeof(s)); }void add(int u, int v, int c, int cost){ //對(duì)兩點(diǎn)之間進(jìn)行單向邊建立edge[cnt].u = u;edge[cnt].v = v;edge[cnt].cost = cost;edge[cnt].c = c;edge[cnt].next = s[u];s[u] = cnt++; //建立單向邊edge[cnt].u = v;edge[cnt].v = u;edge[cnt].cost = -cost;edge[cnt].c = 0;edge[cnt].next = s[v];s[v] = cnt++; //建立雙向邊 }bool spfa(int ss, int ee,int &flow,int &cost){ //以距離為費(fèi)用尋找最短路，以最短路為當(dāng)前增廣路queue<int> q;memset(d, INF, sizeof d);memset(vis, 0, sizeof vis); //初始化d[ss] = 0, vis[ss] = 1, pre[ss] = 0, a[ss] = INF;q.push(ss);while (!q.empty()){ //spfa以費(fèi)用為距離尋找最短路int u = q.front();q.pop();vis[u] = 0;for (int i = s[u]; ~i; i = edge[i].next){ //和當(dāng)前點(diǎn)相連所有邊松弛過(guò)程int v = edge[i].v;if (edge[i].c>0&& d[v]>d[u] + edge[i].cost){ //松弛過(guò)程d[v] = d[u] + edge[i].cost;pre[v] = i;a[v] = min(a[u], edge[i].c); //取最小值if (!vis[v]){vis[v] = 1;q.push(v); //壓入待松弛隊(duì)列}}}}if (d[ee] == INF) return 0; //判斷是否有最短路，無(wú)說(shuō)明最大流完成flow += a[ee];cost += d[ee]*a[ee];int u = ee;while (u != ss){ //求當(dāng)前最短路下的流量和edge[pre[u]].c -= a[ee];edge[pre[u] ^ 1].c += a[ee];u = edge[pre[u]].u;}return 1; }int MCMF(int ss, int ee){ //最小費(fèi)用最大流int cost = 0, flow=0; //初始化while (spfa(ss, ee, flow, cost)); //尋找增廣路徑，直到?jīng)]有增廣路徑為止return cost; //返回最大流費(fèi)用 }struct point{int x,y; //球坐標(biāo)，洞坐標(biāo) };void solve(){point H[107],P[107]; //建立球集與洞集int h=0,p=0;for(int i=0;i<n;i++){ //輸入地圖scanf("%s",&mp[i]);for(int j=0;j<m;j++){if(mp[i][j]=='#'){ //若為洞則坐標(biāo)加入洞集H[h].x=i;H[h].y=j;h++;}else if(mp[i][j]=='@'){ //若為球則坐標(biāo)加入球集P[p].x=i;P[p].y=j;p++;}}}init(); //初始化for(int i=0;i<h;i++)for(int j=0;j<p;j++){int c=fabs(H[i].x-P[j].x)+fabs(H[i].y-P[j].y);add(i+1,h+j+1,1,c);} //建立球與洞之間的路徑for(int i=0;i<h;i++) //建立超級(jí)源點(diǎn)add(0,i+1,1,0);for(int i=0;i<p;i++) //建立超級(jí)匯點(diǎn)add(h+1+i,h+p+1,1,0);printf("%d\n",MCMF(0,h+p+1)); //最小費(fèi)用最大流 }int main(){while(~scanf("%d%d",&n,&m)){if(!(m||n))break;solve(); //解決方案}return 0; }

G、營(yíng)救教練計(jì)劃????????by Amon

tag：動(dòng)態(tài)規(guī)劃、概率DP

// 一道簡(jiǎn)單的期望dp~希望大家喜歡~ #include <cstdio> #include <cstring> #include <map> using namespace std; const int maxn = 1e5 + 10; double dp[maxn];int main(int argc, const char * argv[]) {int n, m, x, y;while (~scanf("%d%d", &n, &m)) {// 初始化 dp 數(shù)組為0memset(dp, 0, sizeof(dp));// 用 map 存儲(chǔ)所有的跳躍點(diǎn)map<int, int> mp;for (int i = 0; i < m; ++i) {scanf("%d%d", &x, &y);mp[x] = y;}// dp[i] 存儲(chǔ)從第i個(gè)位置到 n 需要飛多長(zhǎng)時(shí)間的數(shù)學(xué)期望// n 位置當(dāng)然是 0 啦// 注意，n 后面的幾個(gè)位置也是0dp[n] = 0;for (int i = n - 1; i >= 0; --i) {if (mp.find(i) != mp.end()) {// 如果 i 位置可以直接飛到后面某個(gè)位置，那么他們的期望是相同的dp[i] = dp[mp[i]];} else {// 枚舉后面七個(gè)位置，注意，n 后面的都是0// dp[i] = dp[i+1]/7 + dp[i+2]/7 + dp[i+3]/7 + dp[i+4]/7 + dp[i+5]/7 + dp[i+6]/7 + dp[i+7]/7 + 1double sum = 0;int num = 0;for (int j = i + 1; num < 7; ++j, ++num) {sum += dp[j] + 1;}dp[i] = sum / num;}}printf("%.4lf\n", dp[0]);}return 0; }

H、有種放學(xué)別走????????by huawei

tag：組合數(shù)學(xué)、卡特蘭數(shù)

題目中需要找到正 $2N$ 邊形中，兩個(gè)頂點(diǎn)連線且線段互不相交的方案數(shù)。實(shí)際上就是組合數(shù)學(xué)中的卡特蘭數(shù)。
但是即便不知道何為卡特蘭數(shù)，結(jié)論也非常明顯。
假設(shè)正 $2N$ 邊形中一個(gè)點(diǎn)和另一個(gè)點(diǎn)連線，此時(shí)的多邊形被分為了兩個(gè)部分，此時(shí)方案數(shù)為 [左邊多邊形連線的方案數(shù)] * [右邊多邊形連線的方案數(shù)] 。而一個(gè)點(diǎn)連線的方案有 $N$ 種。因此我們可以得出遞推式：
假設(shè) $F[n]$ 表示 $n$ 邊形連線的方案數(shù)，再加上題目的模，即
$$F[n]=\sum _{i=0}^{n?1}F[i]?F[n?i?1]mod19260817$$

#include <cstdio> const int maxn = 1010; typedef long long LL; const int mod = 19260817; LL f[maxn], n; void init() {f[0] = f[1] = 1;for (int i = 2; i < maxn; i++) {for (int j = 0; j < i; j++) {f[i] = (f[i] + f[j] * f[i - j - 1])%mod;}} } int main() {init();while (scanf("%lld", &n) != EOF) {printf("%lld\n", f[n]);}return 0; }

I、單身狗的尋覓????????by huawei

tag：貪心

此題是結(jié)論明顯的貪心題。
結(jié)論：對(duì)于每一個(gè)人，和他前面的人匹配(如果是異性的情況下)，否則不匹配。
對(duì)于某一個(gè)人而言：
1.如果他能匹配前一個(gè)異性，那么他匹配了前面的異性，匹配對(duì)數(shù) $+1$，如果他不匹配，他被后面匹配，也是對(duì)數(shù) $+1$，即匹配前一個(gè)人對(duì)后續(xù)匹配沒(méi)有不良影響。相反，如果前一個(gè)人可以匹配但卻去匹配后一個(gè)人，可能對(duì)后面匹配產(chǎn)生不良影響。
2.如果他前面無(wú)法匹配，但可以匹配后一個(gè)人，那會(huì)在下一輪判斷中，被后一個(gè)人匹配。
3.如果他完全不能匹配，不匹配對(duì)結(jié)果完全沒(méi)有影響。
但是由于題目數(shù)據(jù)較多，最大為 $10^8$，所以不能使用數(shù)組離線解決，但是我們發(fā)現(xiàn)此題結(jié)果只與前一個(gè)人有關(guān)，因此我們可以考慮在線算法。
題解的做法使用了棧，更簡(jiǎn)便的可以直接int last;來(lái)記錄前一個(gè)人的性別。
此題也有更多做法可以挖掘。

#include <bits/stdc++.h> using namespace std; int main() {int n, x, last;while (scanf("%d", &n) != EOF) {last = -1;int ans = 0;for (int i = 0; i < n; i++) {scanf("%d", &x);if (last == -1) {last = x;} else {if((x%2 + last%2) == 1) {ans++;last = -1;} else {last = x;}}}printf("%d\n", ans);}return 0; }

J、共產(chǎn)主義接班人????????by huawei

tag：線段樹(shù)，模擬

首先我們可以簡(jiǎn)化題目要求，即對(duì)于每一天，都需要查詢一個(gè)小于等于當(dāng)前愛(ài)心指數(shù)的最右邊的家庭，然后記錄個(gè)數(shù)。
因此我們可以考慮用線段樹(shù)維護(hù)區(qū)間家庭操心指數(shù)的最小值，查詢函數(shù)的返回值為最右端的不大于當(dāng)前愛(ài)心指數(shù)的家庭編號(hào)。即對(duì)于每一個(gè)樹(shù)枝節(jié)點(diǎn)，我們優(yōu)先比較右兒子和當(dāng)前愛(ài)心指數(shù)的大小，如果右兒子小于等于愛(ài)心指數(shù)，則說(shuō)明不大于當(dāng)前愛(ài)心指數(shù)的最右的點(diǎn)位于當(dāng)前區(qū)間的右子區(qū)間。如果右兒子比愛(ài)心指數(shù)大，但左兒子小，說(shuō)明在左邊。否則，說(shuō)明不存在比當(dāng)前愛(ài)心指數(shù)小的值。
而且在每一次查詢后，已經(jīng)幫助過(guò)的家庭的操心指數(shù)要設(shè)置為 $INF$，防止重復(fù)查詢。
接下來(lái)就是每天的模擬操作，只需要把每天的幫助家庭戶數(shù)記錄下來(lái)，對(duì)于每個(gè)詢問(wèn)就可以 $O(1)$ 查詢了。

#include <bits/stdc++.h> using namespace std; typedef long long LL; const int INF = 0x3fffffff; const int maxn = 1e5 + 10; LL a[maxn], segtree[maxn << 4], n, m, c, cnt, num, day; LL b[maxn], ans[maxn];void pushup(int now) {segtree[now] = min(segtree[now << 1], segtree[(now << 1)|1]); }void build_tree(int l, int r, int now) {if (l == r) {segtree[now] = a[l];return;}int mid = (l + r)/2;build_tree(l, mid, now << 1);build_tree(mid + 1, r, (now << 1)|1);pushup(now); }int query(int l, int r, int tar, int now) {if (l == r) {segtree[now] = INF;return l;}int mid = (l + r)/2, ans = -1;if (segtree[(now << 1)|1] <= tar) ans = query(mid + 1, r, tar, (now << 1)|1);else if (segtree[now << 1] <= tar) ans = query(l, mid, tar, now << 1);pushup(now);return ans; }int main() {int T;scanf("%d", &T);while (T--) {memset(segtree, 0, sizeof segtree);memset(ans, 0, sizeof ans);memset(a, 0, sizeof a);memset(b, 0, sizeof b);cnt = num = day = 0;scanf("%lld %lld %lld", &n, &m, &c);for (int i = 1; i <= n; i++) {scanf("%lld", &a[i]);}build_tree(1, n, 1);while (num < n) {cnt += c; day++;int k = query(1, n, cnt, 1);while (k != -1) {ans[day]++;cnt -= a[k];k = query(1, n, cnt, 1);}num += ans[day];}for (int i = 0; i < m; i++) {scanf("%lld", &c);printf("%lld\n", c > day? 0 : ans[c]);}}return 0; }

K、66…6????????by Amon

tag：數(shù)論。歐拉函數(shù)、歐拉定理

設(shè)輸入的數(shù)字為 $p$，即題目的要求得一個(gè)長(zhǎng)度為 $x$ 的 $66...6$，使得 $66...6=kp(k\in Z)$。
可以發(fā)現(xiàn)，長(zhǎng)度為 $x$ 的 $66...6$ 可以表示為 $\frac{6(10^x?1)}{9}$。
所以我們可以得到式子$$\frac{6(10^x?1)}{9}=kp$$
即$$6(10^x?1)=9kp$$
為了可以繼續(xù)化簡(jiǎn)，我們假設(shè) $g=gcd(6,9p)$，兩邊同除 $g$。得
$$\frac{6(10^x?1)}{g}=\frac{9kp}{g}$$
此時(shí)$\frac{6}{g}$ 與 $\frac{9kp}{g}$ 互質(zhì)，式子可簡(jiǎn)化為$$10^x?1=\frac{9kp}{g}$$
即求解 $$10^x\equiv 1(mod\frac{9kp}{g})$$
根據(jù)歐拉定理可知，最小的 $x$ 存在于 $\phi (\frac{9kp}{g})$ 的因子中，接下來(lái)的任務(wù)就是枚舉所有 $\phi (\frac{9kp}{g})$ 的因子，從而找到一個(gè)最小的 $x$ 滿足 $10^x\equiv 1(mod\frac{9kp}{g})$。

// sustoj 1908 #include <cstdio> #include <cmath> #include <time.h> #include <cstdlib> using namespace std; typedef long long LL;// 求解歐拉函數(shù) LL phi(LL x) {LL ans = x;for (LL i = 2; i * i <= x; ++i) {if (x % i == 0) {ans = ans / i * (i - 1);while (x % i == 0) {x /= i;}}}if (x > 1) {ans = ans / x * (x - 1);}return ans; }// 快速乘 LL multi(LL a, LL b, LL mod) {LL ret = 0;while (b) {if (b & 1) {ret = (ret + a) % mod;}a = (a << 1) % mod;b >>= 1;}return ret; }// 快速冪 LL fastpow(LL a, LL b, LL p) {LL ans = 1;while (b) {if (b & 1) {ans = multi(ans, a, p);}a = multi(a, a, p);b >>= 1;}return ans; }// 求解最大公約數(shù) LL gcd(LL a, LL b) {return b == 0 ? a : gcd(b, a % b); }int main() {LL p;int ca = 1;while (~scanf("%lld", &p) && p) {printf("Case %d: ", ca++);p /= gcd(p, 6);// p 和 6 有最大公約數(shù)，先約去這個(gè)數(shù)，此時(shí)原題變?yōu)榱?111...111 可以被 p 整除p *= 9;// 此時(shí)原題變?yōu)榱?999...999 可以被 p 整除，即 100...000 - 1 可以被 p 整除// 也就是說(shuō)，100...000 % p 余 1，求最少有多少個(gè) 0// 已知以下定理：// 若正整數(shù) a, p 互質(zhì)，則滿足 a ^ x ≡ 1 (mod p) 的最小的正整數(shù) x0， 是 φ(p) 的約數(shù)（因子）。// φ(p) 為 歐拉函數(shù)，即 10^x ≡ 1 (mod p) 的最小的正整數(shù)解是 φ(p) 的因子if (gcd(p, 10) == 1) {// 互質(zhì)LL ans = phi(p); // 歐拉函數(shù)LL i = 0;int f = 0;LL tmp = sqrt(ans);// 下面這樣求主要是將 O(n) 變?yōu)?O(根號(hào)n)// ans = φ(p)，求 ans 的因子for (i = 1; i * i <= ans; ++i) {// 解在 1 - sqrt(ans) 內(nèi)if (ans % i == 0) {if (fastpow(10, i, p) == 1) {f = 1;break;}}}if (f) {printf("%lld\n", i);} else {// 解在 sqrt(ans) - ans 內(nèi)for (i = tmp; i >= 1; --i) {if (ans % (ans / i) == 0) {if (fastpow(10, ans / i, p) == 1) {break;}}}printf("%lld\n", ans / i);}} else {// 不互質(zhì)，則無(wú)解printf("-1\n");}}return 0; }

總結(jié)

以上是生活随笔為你收集整理的2018 焦作站亚洲区域赛校内选拔赛题解的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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