2017 ACM/ICPC Asia Regional Qingdao Online Apple The Dominator of Strings Chinese Zodiac Smallest Minimum Cut A Cubic number and A Cubic Number
Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 65535/32768 K (Java/Others)
Total Submission(s): 982 Accepted Submission(s): 323
Total Submission(s): 982 Accepted Submission(s): 323
Problem Description
Apple is Taotao's favourite fruit. In his backyard, there are three apple trees with coordinates ) of the new tree. Could you tell him if it is outside the circle or not?
Input
The first line contains an integer 000.
It is guaranteed that, any three of the four positions do not lie on a straight line.
It is guaranteed that, any three of the four positions do not lie on a straight line.
Output
For each case, output "Accepted" if the position is outside the circle, or "Rejected" if the position is on or inside the circle.
Sample Input
3
-2 0 0 -2 2 0 2 -2
-2 0 0 -2 2 0 0 2
-2 0 0 -2 2 0 1 1
Sample Output
Accepted
Rejected
Rejected
Source
圆的反演,java大数走一波
其实用外接圆半径及点那个不复杂的东西也可以玩
import java.io.*; import java.util.*; import java.math.*; public class Main { static public BigInteger xu[]=new BigInteger[4]; static public BigInteger xd[]=new BigInteger[4]; static public BigInteger yu[]=new BigInteger[4]; static public BigInteger yd[]=new BigInteger[4]; static public void main(String[] args) { Scanner cin=new Scanner(System.in); int T=cin.nextInt(); while(T-->0) { for(int i=0;i<4;i++) { xu[i]=cin.nextBigInteger(); yu[i]=cin.nextBigInteger(); xd[i]=BigInteger.ONE; yd[i]=BigInteger.ONE; } for(int i=1;i<4;i++) { xu[i]=xu[i].subtract(xu[0]); yu[i]=yu[i].subtract(yu[0]); } for(int i=1;i<4;i++) { xd[i]=xu[i].multiply(xu[i]).add(yu[i].multiply(yu[i])); yd[i]=xu[i].multiply(xu[i]).add(yu[i].multiply(yu[i])); } BigInteger t=xu[1].multiply(yu[2]).subtract(yd[1].multiply(xd[2])); t=t.subtract(yu[1].multiply(xu[2]).subtract(xd[1].multiply(yd[2]))); if(t.compareTo(BigInteger.ZERO)<0) { t=xu[1];xu[1]=xu[2];xu[2]=t; t=yu[1];yu[1]=yu[2];yu[2]=t; t=xd[1];xd[1]=xd[2];xd[2]=t; t=yd[1];yd[1]=yd[2];yd[2]=t; } for(int i=2;i<=3;i++) { xu[i]=xu[i].multiply(xd[1]).subtract(xu[1].multiply(xd[i])); xd[i]=xd[i].multiply(xd[1]); yu[i]=yu[i].multiply(yd[1]).subtract(yu[1].multiply(yd[i])); yd[i]=yd[i].multiply(yd[1]); } t=xu[3].multiply(yu[2]).subtract(yd[3].multiply(xd[2])); t=t.subtract(yu[3].multiply(xu[2]).subtract(xd[3].multiply(yd[2]))); if(t.compareTo(BigInteger.ZERO)>=0)System.out.println("Rejected"); else System.out.println("Accepted"); } } }
The Dominator of Strings
Time Limit: 3000/3000 MS (Java/Others) Memory Limit: 65535/32768 K (Java/Others)
Total Submission(s): 6778 Accepted Submission(s): 713
Problem Description
Here you have a set of strings. A dominator is a string of the set dominating all strings else. The string T.
Input
The input contains several test cases and the first line provides the total number of cases.
For each test case, the first line contains an integer 100000.
The limit is 30MB for the input file.
For each test case, the first line contains an integer 100000.
The limit is 30MB for the input file.
Output
For each test case, output a dominator if exist, or No if not.
Sample Input
3
10
you
better
worse
richer
poorer
sickness
health
death
faithfulness
youbemyweddedwifebetterworsericherpoorersicknesshealthtilldeathdouspartandpledgeyoumyfaithfulness
5
abc
cde
abcde
abcde
bcde
3
aaaaa
aaaab
aaaac
Sample Output
youbemyweddedwifebetterworsericherpoorersicknesshealthtilldeathdouspartandpledgeyoumyfaithfulness
abcde
No
从较长串中找子串的
自动机的复杂度太高,挑战上的代码就可以过得
这个暴力strstr也可以过,也就是KMP,一定是我太丑了
#include<bits/stdc++.h> using namespace std; const int MAXN = 100010; int n,k; int Paiming[MAXN+1],tmp[MAXN+1]; int flag; bool comp_sa(int i, int j) { if(Paiming[i] != Paiming[j]) return Paiming[i] < Paiming[j]; else{ int ri = i+k <= n? Paiming[i+k] : -1; int rj = j+k <= n? Paiming[j+k] : -1; return ri < rj; } } void calc_sa(string &S, int *sa) { n = S.size(); for(int i = 0; i <= n; i++) { sa[i] = i; Paiming[i] = i < n ? S[i] : -1; } for( k =1; k <= n; k *= 2) { sort(sa,sa+n+1,comp_sa); tmp[sa[0]] = 0; for(int i = 1; i <= n; i++) { tmp[sa[i]] = tmp[sa[i-1]] + (comp_sa(sa[i-1],sa[i]) ? 1: 0); } for(int i = 0; i <= n; i++) { Paiming[i] = tmp[i]; } } } int SuffixArrayMatch(string &S, int *sa, string T) { int lhs = 0, rhs = S.size(); while(rhs - lhs > 1) { int mid = (lhs + rhs)>>1; if(S.compare(sa[mid],T.size(),T) < 0) lhs = mid; else rhs=mid; } return S.compare(sa[rhs],T.size(),T) == 0; } int main() { int t; ios::sync_with_stdio(false); cin>>t; string s[100010],longs; while(t--){ int n,l=-1,p=-1,i; cin>>n; memset(Paiming,0,sizeof Paiming); memset(tmp,0,sizeof tmp); for(i=0;i<n;i++){ cin>>s[i]; int len=s[i].size(); if(len>l){ l=len; longs=s[i]; p=i; } } if(n==1){ cout<<longs<<endl; continue; } int *sa = new int[longs.size()+1]; calc_sa(longs,sa); for(i=0;i<n;i++){ if(p==i)continue; if(!SuffixArrayMatch(longs,sa,s[i])) break; } //delete [] sa; sa = NULL; if(i>=n){ cout<<longs<<endl; }else { cout<<"No"<<endl; } } }
Chinese Zodiac
Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 65535/32768 K (Java/Others)Total Submission(s): 2451 Accepted Submission(s): 1645
Problem Description
The Chinese Zodiac, known as Sheng Xiao, is based on a twelve-year cycle, each year in the cycle related to an animal sign. These signs are the rat, ox, tiger, rabbit, dragon, snake, horse, sheep, monkey, rooster, dog and pig.
Victoria is married to a younger man, but no one knows the real age difference between the couple. The good news is that she told us their Chinese Zodiac signs. Their years of birth in luner calendar is not the same. Here we can guess a very rough estimate of the minimum age difference between them.
If, for instance, the signs of Victoria and her husband are ox and rabbit respectively, the estimate should be 12 years.
Victoria is married to a younger man, but no one knows the real age difference between the couple. The good news is that she told us their Chinese Zodiac signs. Their years of birth in luner calendar is not the same. Here we can guess a very rough estimate of the minimum age difference between them.
If, for instance, the signs of Victoria and her husband are ox and rabbit respectively, the estimate should be 12 years.
Input
The first line of input contains an integer ) indicating the number of test cases.
For each test case a line of two strings describes the signs of Victoria and her husband.
For each test case a line of two strings describes the signs of Victoria and her husband.
Output
For each test case output an integer in a line.
Sample Input
3
ox rooster
rooster ox
dragon dragon
Sample Output
8
4
12
中国生肖,随手模拟就可以了
#include<stdio.h> #include<string.h> #include<math.h> #include<stdlib.h> using namespace std; int main() { char m[12][10]={ "rat", "ox", "tiger", "rabbit", "dragon", "snake", "horse", "sheep", "monkey", "rooster", "dog" , "pig" }; int t,s; scanf("%d",&t); while(t--){ char p[10],q[10]; scanf("%s%s",&p,&q); if(strcmp(p,q)==0){ puts("12"); }else { int i,pp,qq; for(i=0;i<12;i++){ if(strcmp(m[i],p)==0){ pp=i; } if(strcmp(m[i],q)==0){ qq=i; } } s=(pp-qq); if(s>0){ s=s-12; } printf("%d ",-s); } } }
Smallest Minimum Cut
Time Limit: 2000/2000 MS (Java/Others) Memory Limit: 65535/32768 K (Java/Others)Total Submission(s): 3297 Accepted Submission(s): 602
Problem Description
Consider a network E with all edges connecting nodes in different parts. A minimum cut is the one whose cut set has the minimum summation of capacities. The size of a cut is the number of edges in the cut set. Please calculate the smallest size of all minimum cuts.
Input
The input contains several test cases and the first line is the total number of cases w.
Output
For each test case, output the smallest size of all minimum cuts in a line.
Sample Input
2
4 5
1 4
1 2 3
1 3 1
2 3 1
2 4 1
3 4 2
4 5
1 4
1 2 3
1 3 1
2 3 1
2 4 1
3 4 3
Sample Output
2
3
求点s到点t的最小割,这个网上就有一道一样的题吧
dinic是过不去的,要用sap算法
#include<bits/stdc++.h> using namespace std; typedef long long ll; #define MAXN 2333 #define MAXM 2333333 struct Edge { int v,next; ll cap; } edge[MAXM]; int head[MAXN],pre[MAXN],cur[MAXN],level[MAXN],gap[MAXN],NV,NE,n,m,vs,vt; void ADD(int u,int v,ll cap,ll cc=0) { edge[NE].v=v; edge[NE].cap=cap; edge[NE].next=head[u]; head[u]=NE++; edge[NE].v=u; edge[NE].cap=cc; edge[NE].next=head[v]; head[v]=NE++; } ll SAP(int vs,int vt) { memset(pre,-1,sizeof(pre)); memset(level,0,sizeof(level)); memset(gap,0,sizeof(gap)); for(int i=0; i<=NV; i++)cur[i]=head[i]; int u=pre[vs]=vs; ll aug=-1,maxflow=0; gap[0]=NV; while(level[vs]<NV) { loop: for(int &i=cur[u]; i!=-1; i=edge[i].next) { int v=edge[i].v; if(edge[i].cap&&level[u]==level[v]+1) { aug==-1?aug=edge[i].cap:aug=min(aug,edge[i].cap); pre[v]=u; u=v; if(v==vt) { maxflow+=aug; for(u=pre[u]; v!=vs; v=u,u=pre[u]) { edge[cur[u]].cap-=aug; edge[cur[u]^1].cap+=aug; } aug=-1; } goto loop; } } int minlevel=NV; for(int i=head[u]; i!=-1; i=edge[i].next) { int v=edge[i].v; if(edge[i].cap&&minlevel>level[v]) { cur[u]=i; minlevel=level[v]; } } if(--gap[level[u]]==0)break; level[u]=minlevel+1; gap[level[u]]++; u=pre[u]; } return maxflow; } int main() { int T,u,v,w; scanf("%d",&T); while(T--) { scanf("%d%d",&n,&m); scanf("%d%d",&vs,&vt); NV=n,NE=0; memset(head,-1,sizeof(head)); for(int i=1; i<=m; i++) { scanf("%d%d%d",&u,&v,&w); ADD(u,v,(ll)w*MAXM+1); } ll ans=SAP(vs,vt); printf("%d ",ans%MAXM); } return 0; }
A Cubic number and A Cubic Number
Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 65535/32768 K (Java/Others)Total Submission(s): 4947 Accepted Submission(s): 1346
Problem Description
A cubic number is the result of using a whole number in a multiplication three times. For example, p is a difference of two cubic numbers.
Input
The first of input contains an integer ).
Output
For each test case, output 'YES' if given p is a difference of two cubic numbers, or 'NO' if not.
Sample Input
10
2
3
5
7
11
13
17
19
23
29
Sample Output
NO
NO
NO
YES
NO
NO
NO
YES
NO
这个我是机房第一个做出来的啊,让你看一个数是不是两个数的立方差
但是这个数是质数,因式分解判断另一段就好的
直接二分答案存不存在就好
#include<bits/stdc++.h> using namespace std; typedef long long LL; bool la(LL x) { LL l=1,r=1e6+5; while(l<=r) { LL mi=(l+r)/2; LL y=mi-1; if(mi*mi+y*y+mi*y==x) return 1; else if(mi*mi+y*y+mi*y<x) l=mi+1; else r=mi-1; } return 0; } int main() { int T; scanf("%d",&T); while(T--) { LL n; scanf("%lld",&n); printf("%s ",la(n)?"YES":"NO"); } return 0; }