2018/02/26 模拟赛
第一题排序暴力
1 #include<iostream> 2 #include<cstring> 3 #include<cstdio> 4 #include<string> 5 #include<algorithm> 6 #include<cmath> 7 #include<utility> 8 #include<stdio.h> 9 #include<cstdlib> 10 #include<iomanip> //cout<<setiosflags(ios::fixed)<<setprecision(2); 11 #include<ctime> //double a=(double)clock(); cout<<a<<endl; 12 #include<vector> 13 #include<queue> 14 #include<set> 15 #include<map> 16 using namespace std; 17 int read(){ 18 int x=0,ff=1;char ch=getchar(); 19 while(ch>'9'||ch<'0'){if(ch=='-')ff=-1; ch=getchar();} 20 while(ch<='9'&&ch>='0'){x=x*10+ch-'0';ch=getchar();} 21 return ff*x; 22 } 23 map<int,int>mp; 24 int N,a,b[100010]; 25 long long ans; 26 int main(){ 27 freopen("expedition.in","r",stdin); 28 freopen("expedition.out","w",stdout); 29 N=read(); 30 for(int i=1;i<=N;i++){ 31 a=read(),b[i]=read(); 32 mp[b[i]]+=a; 33 } 34 sort(b+1,b+1+N); 35 for(int i=1;i<=N;i++) 36 if(b[i]!=b[i-1]) 37 ans+=1LL*mp[b[i]]*mp[b[i]]; 38 printf("%I64d ",ans); 39 return 0; 40 }
第二题计算表达式，对于多项式用类似高精度的方法计算
1 #include<iostream> 2 #include<cstring> 3 #include<cstdio> 4 #include<string> 5 #include<algorithm> 6 #include<cmath> 7 #include<utility> 8 #include<stdio.h> 9 #include<cstdlib> 10 #include<iomanip> //cout<<setiosflags(ios::fixed)<<setprecision(2); 11 #include<ctime> //double a=(double)clock(); cout<<a<<endl; 12 #include<vector> 13 #include<queue> 14 using namespace std; 15 int read(){ 16 int x=0,ff=1;char ch=getchar(); 17 while(ch>'9'||ch<'0'){if(ch=='-')ff=-1; ch=getchar();} 18 while(ch<='9'&&ch>='0'){x=x*10+ch-'0';ch=getchar();} 19 return ff*x; 20 } 21 const int MOD=10007; 22 struct bignum{ 23 int num[510]; 24 int len; 25 void clear() 26 {len=0,memset(num,0,sizeof(num));} 27 void print(){ 28 printf("%d ",len); 29 for(int i=0;i<=len;i++){ 30 if(num[i]<0) 31 num[i]+=MOD; 32 printf("%d ",num[i]); 33 } 34 } 35 bignum friend operator+(const bignum&A,const bignum&B){ 36 bignum C; 37 C.len=max(A.len,B.len); 38 for(int i=0;i<=C.len;i++){ 39 if(i>A.len) 40 C.num[i]=B.num[i]; 41 else if(i>B.len) 42 C.num[i]=A.num[i]; 43 else 44 C.num[i]=(A.num[i]+B.num[i])%MOD; 45 } 46 while(C.num[C.len]==0&&C.len) 47 C.len--; 48 return C; 49 } 50 bignum friend operator-(const bignum&A,const bignum&B){ 51 bignum C; 52 C.len=max(A.len,B.len); 53 for(int i=0;i<=C.len;i++){ 54 if(i>A.len) 55 C.num[i]=-B.num[i]; 56 else if(i>B.len) 57 C.num[i]=A.num[i]; 58 else 59 C.num[i]=(A.num[i]-B.num[i])%MOD; 60 } 61 while(C.num[C.len]==0&&C.len) 62 C.len--; 63 return C; 64 } 65 bignum friend operator*(const bignum&A,const bignum&B){ 66 bignum C; 67 C.clear(); 68 for(int i=0;i<=A.len;i++) 69 for(int j=0;j<=B.len;j++){ 70 int k=i+j; 71 C.num[k]+=A.num[i]*B.num[j]; 72 C.num[k]%=MOD; 73 if(k>C.len&&C.num[k]!=0) 74 C.len=k; 75 } 76 return C; 77 } 78 }p[1010],t;//多项式栈 79 char s[1010]; 80 int N; 81 char op[1010];//operator 运算符栈 82 int to,tp; 83 inline int grade(char c){ 84 if(c=='+'||c=='-') 85 return 1; 86 else if(c=='*') 87 return 2; 88 else 89 return 0; 90 } 91 int main(){ 92 freopen("simplify.in","r",stdin); 93 freopen("simplify.out","w",stdout); 94 gets(s+1); 95 N=strlen(s+1); 96 for(int i=1;i<=N;i++){ 97 if(s[i]=='x'){ 98 tp++; 99 p[tp].len=1; 100 p[tp].num[0]=0; 101 p[tp].num[1]=1; 102 } 103 else if(s[i]>='0'&&s[i]<='9'){ 104 int j=i,temp=0; 105 while(s[j]>='0'&&s[j]<='9'){ 106 temp=temp*10+s[j]-'0'; 107 j++; 108 } 109 tp++; 110 p[tp].len=0; 111 p[tp].num[0]=temp; 112 i=j-1; 113 } 114 else{ 115 if(s[i]=='(') 116 op[++to]=s[i]; 117 else if(s[i]==')'){ 118 while(to&&op[to]!='('){ 119 tp--; 120 if(op[to]=='+') 121 p[tp]=p[tp]+p[tp+1]; 122 else if(op[to]=='-') 123 p[tp]=p[tp]-p[tp+1]; 124 else 125 p[tp]=p[tp]*p[tp+1]; 126 to--; 127 } 128 to--; 129 } 130 else{ 131 while(to&&grade(op[to])>=grade(s[i])){ 132 tp--; 133 if(op[to]=='+') 134 p[tp]=p[tp]+p[tp+1]; 135 else if(op[to]=='-') 136 p[tp]=p[tp]-p[tp+1]; 137 else 138 p[tp]=p[tp]*p[tp+1]; 139 to--; 140 } 141 op[++to]=s[i]; 142 } 143 } 144 } 145 while(to){ 146 tp--; 147 if(op[to]=='+') 148 p[tp]=p[tp]+p[tp+1]; 149 else if(op[to]=='-') 150 p[tp]=p[tp]-p[tp+1]; 151 else 152 p[tp]=p[tp]*p[tp+1]; 153 to--; 154 } 155 p[tp].print(); 156 return 0; 157 }