鏈接。
【A】尋找漂亮數字
題意:
給定了兩列非零數字。
我們說一個數是漂亮的,當它的十進制表達中有至少一個數從數列一中取出,至少有一個數從數列二中取出。
最小的漂亮數字是多少?
輸入:
codeforces進不去。第一行兩個數\(n,m(1\leq n,m\leq9)\),表示數列一、二的長度。
第二行n個數,表示數列一。
第三行m個數,表示數列二。
題解:
1 #include<cstdio> 2 #include<algorithm> 3 #include<cstring> 4 #include<set> 5 #define F(i,a,b) for(int i=a;i<=b;++i) 6 #define dF(i,a,b) for(int i=a;i>=b;--i) 7 #define F2(i,a,b) for(int i=a;i<b;++i) 8 inline int Min(int p,int q){return p<q?p:q;} 9 inline int Max(int p,int q){return p>q?p:q;} 10 int n,m,a[10],b[10],A=100,B=100; 11 void init(){ 12 int x; 13 scanf("%d%d",&n,&m); 14 F(i,1,n) scanf("%d",&x), a[x]=1, A=Min(A,x); 15 F(i,1,m) scanf("%d",&x), b[x]=1, B=Min(B,x); 16 } 17 int main(){ 18 init(); 19 F(i,1,9) if(a[i]&&b[i]) {printf("%d",i); return 0;} 20 if(A>B) printf("%d%d",B,A); 21 else printf("%d%d",A,B); 22 return 0; 23 }
【B】最小值的最大值的最大值
題意:
給定了一個數組和一個數k,你要把這個數組分成恰好k份,使得這k份中的每一份的最小值的最大值最大。
求出這個最大值。
輸入:
codeforces是什么比賽?第一行,兩個數n,k。
第二行,n個數,表示數組中的元素。
輸出:
一個數,表示最大值。
題解:
當k=1時,答案是最小值。當k>=3時,答案是最大值。
當k=2時,枚舉分割點。
1 #include<cstdio> 2 #include<algorithm> 3 #include<cstring> 4 #include<set> 5 #define F(i,a,b) for(int i=a;i<=b;++i) 6 #define dF(i,a,b) for(int i=a;i>=b;--i) 7 #define F2(i,a,b) for(int i=a;i<b;++i) 8 inline int Min(int p,int q){return p<q?p:q;} 9 inline int Max(int p,int q){return p>q?p:q;} 10 int n,k,a[100001],min=2147483647,max=-2147483647; 11 int m1[100001],m2[100001]; 12 void init(){ 13 scanf("%d%d",&n,&k); 14 F(i,1,n) scanf("%d",a+i), max=Max(max,a[i]), min=Min(min,a[i]); 15 } 16 int main(){ 17 init(); 18 if(k>=3) printf("%d",max); 19 else if(k==1) printf("%d",min); 20 else{ 21 m1[1]=a[1]; F(i,2,n) m1[i]=Min(m1[i-1],a[i]); 22 m2[n]=a[n]; dF(i,n-1,1) m2[i]=Min(m2[i+1],a[i]); 23 int Ans=-2147483647; 24 F(i,2,n) Ans=Max(Ans,Max(m1[i-1],m2[i])); 25 printf("%d",Ans); 26 } 27 return 0; 28 }
【C】最大分割
codeforces怎么提交、題意:
給你一個數n,把它分成若干個合數的和,最多能分成多少個合數?有多組數據。
輸入:
第一行一個數q(1<=q<=10^5),表示數據組數。
對于每個數據,輸入一個數n(1<=n<=10^9)。
輸出:
對于每組數據,輸出一行一個數表示分割數。如果無法做到,輸出-1。
codeforces比賽時間、題解:
4是最小的合數,對于n足夠大的情況,可以分成若干4和一些較小的合數。
于是對4的余數分類討論。具體看代碼。
1 #include<cstdio> 2 #include<algorithm> 3 #include<cstring> 4 #include<set> 5 #define F(i,a,b) for(int i=a;i<=b;++i) 6 #define dF(i,a,b) for(int i=a;i>=b;--i) 7 #define F2(i,a,b) for(int i=a;i<b;++i) 8 inline int Min(int p,int q){return p<q?p:q;} 9 inline int Max(int p,int q){return p>q?p:q;} 10 int T,n; 11 int main(){ 12 scanf("%d",&T); 13 while(T--){ 14 scanf("%d",&n); 15 switch(n%4){ 16 case 0: printf("%d\n",n/4);break; 17 case 1: {n>=9?printf("%d\n",(n-9)/4+1):puts("-1");break;} 18 case 2: {n>=6?printf("%d\n",(n-6)/4+1):puts("-1");break;} 19 case 3: {n>=15?printf("%d\n",(n-15)/4+2):puts("-1");break;} 20 } 21 } 22 return 0; 23 }
【D】和區間與異或有關的東西
不會。
【E】點、線什么的和現成的標題
題意:
codeforces刷題。平面直角坐標系中有一些格點,你可以過每個格點畫出關于x軸或y軸平行的直線,也可以不畫,問有最終多少種不同的畫法,重合的直線算作同一條。
輸入:
第一行,一個數n(1<=n<=10^5),表示格點的個數。
接下來n行,每行兩個數xi, yi,表示第i個點的坐標是(xi,yi)。保證沒有重合的點。
輸出:
一個數,畫法總數對10^9+7取模的結果。
codeforces分數規則。題解:
只有橫坐標或縱坐標相同的點才會互相影響,而互相影響的關系是傳遞的。
我們先把不會互相影響的點分開,最終的答案是每一部分的答案的乘積。
那么現在我們有一堆互相影響的點,如何計算方案數?
參見http://www.cnblogs.com/kkkkahlua/p/7679526.html和http://hzwer.com/2950.html。嘻嘻。
代碼也是抄的,嚶嚶嚶。
1 #include <bits/stdc++.h> 2 #define maxn 100010 3 using namespace std; 4 typedef long long LL; 5 const LL mod = 1e9+7; 6 struct node { 7 int x, y; 8 }a[maxn]; 9 int fa[maxn], sz[maxn], f[maxn], id[maxn], m[maxn]; 10 bool circ[maxn], vis[maxn]; 11 vector<int> v[maxn]; 12 set<int> sx, sy; 13 bool cmp1(int i, int j) { 14 return a[i].x < a[j].x || (a[i].x == a[j].x && a[i].y < a[j].y); 15 } 16 bool cmp2(int i, int j) { 17 return a[i].y < a[j].y || (a[i].y == a[j].y && a[i].x < a[j].x); 18 } 19 LL poww(LL a, LL b) { 20 LL ret = 1; 21 while (b) { 22 if (b & 1) (ret *= a) %= mod; 23 (a *= a) %= mod; 24 b >>= 1; 25 } 26 return ret; 27 } 28 int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); } 29 void unionn(int a, int b) { 30 a = find(a), b = find(b); 31 if (a == b) { circ[a] = true; return; } 32 if (sz[a] > sz[b]) swap(a, b); 33 fa[a] = b; sz[b] += sz[a]; 34 circ[b] |= circ[a]; 35 } 36 int main() { 37 int n; 38 scanf("%d", &n); 39 for (int i = 0; i < n; ++i) { 40 scanf("%d%d", &a[i].x, &a[i].y); 41 } 42 for (int i = 0; i < n; ++i) id[i] = i; 43 for (int i = 0; i < n; ++i) fa[i] = i, sz[i] = 1; 44 45 sort(id, id+n, cmp1); 46 for (int i = 1; i < n; ++i) { 47 if (a[id[i]].x == a[id[i-1]].x) unionn(id[i-1], id[i]); 48 } 49 sort(id, id+n, cmp2); 50 for (int i = 1; i < n; ++i) { 51 if (a[id[i]].y == a[id[i-1]].y) unionn(id[i-1], id[i]); 52 } 53 for (int i = 0; i < n; ++i) fa[i] = find(i); 54 55 int tot = -1; 56 for (int i = 0; i < n; ++i) { 57 if (!vis[fa[i]]) vis[fa[i]] = true, f[++tot] = fa[i], m[fa[i]] = tot; 58 v[m[fa[i]]].push_back(i); 59 } 60 LL ans = 1; 61 for (int i = 0; i <= tot; ++i) { 62 sx.clear(), sy.clear(); 63 for (auto idx : v[i]) { 64 sx.insert(a[idx].x), sy.insert(a[idx].y); 65 } 66 LL mul = poww(2, sx.size()+sy.size()); 67 if (!circ[f[i]]) (mul += mod-1) %= mod; 68 (ans *= mul) %= mod; 69 } 70 printf("%I64d\n", ans); 71 return 0; 72 }