2015 Multi-University Training Contest 5
分类:
IT文章
•
2022-07-16 21:19:19
1001 MZL's Circle Zhou
1002 MZL's xor
水题中最后一个做的。因为看成i<j了。
后来听学长说才发现i可以等于j。真是orz。
1 # include <iostream>
2 # include <cstdio>
3 using namespace std;
4 typedef long long LL;
5
6 int main(void)
7 {
8 int T; cin>>T;
9 while(T--)
10 {
11 LL n,m,z,l;
12 scanf("%I64d%I64d%I64d%I64d",&n,&m,&z,&l);
13 LL ans=0,A=0;
14 for(int i=1;i<n;i++)
15 {
16 A=(A*m+z)%l;
17 ans=ans^(2*A);
18 }
19 printf("%I64d
",ans);
20 }
21 return 0;
22 }
Aguin
1003 MZL's combat
1004 MZL's game
1005 MZL's chemistry
我就是脏。怎样阿。咬我阿。
1 # include <iostream>
2 # include <cstdio>
3 using namespace std;
4 double e1[20]={0,13.59,24.58,5.39,9.32,8.29,11.26,14.53,13.61,17.42,
5 21.56,5.13,7.64,5.98,8.15,10.48,10.36,12.96,15.75};
6 double e2[6]={11.81,13.99,10.45,12.12,9.6,10.74};
7
8 int main(void)
9 {
10 int u,v,eu,ev;
11 while((scanf("%d%d",&u,&v))!=EOF)
12 {
13 if(u<=18) eu=e1[u];
14 else if(u==35) eu=e2[0];
15 else if(u==36) eu=e2[1];
16 else if(u==53) eu=e2[2];
17 else if(u==54) eu=e2[3];
18 else if(u==85) eu=e2[4];
19 else if(u==86) eu=e2[5];
20 if(v<=18) ev=e1[v];
21 else if(v==35) ev=e2[0];
22 else if(v==36) ev=e2[1];
23 else if(v==53) ev=e2[2];
24 else if(v==54) ev=e2[3];
25 else if(v==85) ev=e2[4];
26 else if(v==86) ev=e2[5];
27 if(eu>ev) puts("FIRST BIGGER");
28 else puts("SECOND BIGGER");
29 }
30 return 0;
31 }
Aguin
1006 MZL's endless loop
最后一小时在码。最后一分钟交RE。
原因是之前在做树dp。习惯性边开2maxn。
赛后交吃T。看题解发现没有删边。
加了一行 headlist[tem]=edge[i].pre 删边。
就……过……了。啊~啊~西湖的水~我的泪……
另外做法和题解略不同。
先找奇数的点出发。不管走树还是环都可以。
剩下全是偶数的点。就全部是环了。
1 # include <iostream>
2 # include <cstdio>
3 # include <cstring>
4 # include <algorithm>
5 using namespace std;
6 # define maxn 100100
7 int n,m,odd,even;
8 int cnt,headlist[maxn],deg[maxn];
9
10 struct node
11 {
12 int to,val,pre;
13 } edge[maxn*6];
14
15 void add(int from,int to,int val)
16 {
17 cnt++;
18 edge[cnt].pre=headlist[from];
19 edge[cnt].to=to;
20 edge[cnt].val=val;
21 headlist[from]=cnt;
22 return;
23 }
24
25 int findodd(void)
26 {
27 for(int i=odd;i<=n;i++)
28 if(deg[i]%2) return odd=i;
29 return 0;
30 }
31
32 int findeven(void)
33 {
34 for(int i=even;i<=n;i++)
35 if(deg[i]) return even=i;
36 return 0;
37 }
38
39 void draw(int x)
40 {
41 int tem=x;
42 while(deg[tem])
43 {
44 int next=0,i,to;
45 for(i=headlist[tem];i;i=edge[i].pre)
46 {
47 headlist[tem]=edge[i].pre;
48 if(edge[i].val>=0) continue;
49 to=edge[i].to;
50 if(deg[to]) {next=to; break;}
51 }
52 if(next)
53 {
54 deg[to]--; deg[tem]--;
55 if(i%2) {edge[i].val=1; edge[i+1].val=0;}
56 else {edge[i].val=1; edge[i-1].val=0;}
57 tem=next;
58 }
59 }
60 return;
61 }
62
63 int main(void)
64 {
65 int T; cin>>T;
66 while(T--)
67 {
68 cnt=0; odd=even=1;
69 memset(headlist,0,sizeof(headlist));
70 memset(deg,0,sizeof(deg));
71 scanf("%d%d",&n,&m);
72 for(int i=1;i<=m;i++)
73 {
74 int u,v; scanf("%d%d",&u,&v);
75 add(u,v,-1);
76 add(v,u,-1);
77 deg[u]++; deg[v]++;
78 }
79 int x;
80 while(x=findodd()) draw(x);
81 while(x=findeven()) draw(x);
82 for(int i=1;i<=2*m-1;i+=2)
83 printf("%d
",edge[i].val);
84 }
85 return 0;
86 }
Aguin
1007 MZL's simple problem
想都没想就把set扔进去的sb。好心的高中生没有卡我。
1 # include <iostream>
2 # include <cstdio>
3 # include <set>
4 using namespace std;
5 multiset<int> s;
6 multiset<int>::iterator it;
7
8 int main(void)
9 {
10 int N;
11 scanf("%d",&N);
12 for(int i=1;i<=N;i++)
13 {
14 int x,y;
15 scanf("%d",&x);
16 if(x==1)
17 {
18 scanf("%d",&y);
19 s.insert(y);
20 }
21 else if(x==2)
22 {
23 if(!s.empty())
24 {
25 it=s.begin();
26 s.erase(it);
27 }
28 }
29 else
30 {
31 if(!s.empty())
32 printf("%d
",*s.rbegin());
33 else puts("0");
34 }
35 }
36 return 0;
37 }
Aguin
1 #include<iostream>
2 #include<cstdio>
3 #include<string>
4 #include<cstring>
5 #include<iomanip>
6 #include<algorithm>
7 using namespace std;
8
9 #define MAXN 9999
10 #define MAXSIZE 10
11 #define DLEN 4
12
13 class BigNum
14 {
15 private:
16 int a[500]; //可以控制大数的位数
17 int len; //大数长度
18 public:
19 BigNum(){ len = 1;memset(a,0,sizeof(a)); } //构造函数
20 BigNum(const int); //将一个int类型的变量转化为大数
21 BigNum(const char*); //将一个字符串类型的变量转化为大数
22 BigNum(const BigNum &); //拷贝构造函数
23 BigNum &operator=(const BigNum &); //重载赋值运算符,大数之间进行赋值运算
24
25 friend istream& operator>>(istream&, BigNum&); //重载输入运算符
26 friend ostream& operator<<(ostream&, BigNum&); //重载输出运算符
27
28 BigNum operator+(const BigNum &) const; //重载加法运算符,两个大数之间的相加运算
29 BigNum operator-(const BigNum &) const; //重载减法运算符,两个大数之间的相减运算
30 BigNum operator*(const BigNum &) const; //重载乘法运算符,两个大数之间的相乘运算
31 BigNum operator/(const int &) const; //重载除法运算符,大数对一个整数进行相除运算
32
33 BigNum operator^(const int &) const; //大数的n次方运算
34 long long operator%(const long long &) const; //大数对一个int类型的变量进行取模运算
35 bool operator>(const BigNum & T)const; //大数和另一个大数的大小比较
36 bool operator>(const int & t)const; //大数和一个int类型的变量的大小比较
37
38 void print(); //输出大数
39 };
40 BigNum::BigNum(const int b) //将一个int类型的变量转化为大数
41 {
42 int c,d = b;
43 len = 0;
44 memset(a,0,sizeof(a));
45 while(d > MAXN)
46 {
47 c = d - (d / (MAXN + 1)) * (MAXN + 1);
48 d = d / (MAXN + 1);
49 a[len++] = c;
50 }
51 a[len++] = d;
52 }
53 BigNum::BigNum(const char*s) //将一个字符串类型的变量转化为大数
54 {
55 int t,k,index,l,i;
56 memset(a,0,sizeof(a));
57 l=strlen(s);
58 len=l/DLEN;
59 if(l%DLEN)
60 len++;
61 index=0;
62 for(i=l-1;i>=0;i-=DLEN)
63 {
64 t=0;
65 k=i-DLEN+1;
66 if(k<0)
67 k=0;
68 for(int j=k;j<=i;j++)
69 t=t*10+s[j]-'0';
70 a[index++]=t;
71 }
72 }
73 BigNum::BigNum(const BigNum & T) : len(T.len) //拷贝构造函数
74 {
75 int i;
76 memset(a,0,sizeof(a));
77 for(i = 0 ; i < len ; i++)
78 a[i] = T.a[i];
79 }
80 BigNum & BigNum::operator=(const BigNum & n) //重载赋值运算符,大数之间进行赋值运算
81 {
82 int i;
83 len = n.len;
84 memset(a,0,sizeof(a));
85 for(i = 0 ; i < len ; i++)
86 a[i] = n.a[i];
87 return *this;
88 }
89 istream& operator>>(istream & in, BigNum & b) //重载输入运算符
90 {
91 char ch[MAXSIZE*4];
92 int i = -1;
93 in>>ch;
94 int l=strlen(ch);
95 int count=0,sum=0;
96 for(i=l-1;i>=0;)
97 {
98 sum = 0;
99 int t=1;
100 for(int j=0;j<4&&i>=0;j++,i--,t*=10)
101 {
102 sum+=(ch[i]-'0')*t;
103 }
104 b.a[count]=sum;
105 count++;
106 }
107 b.len =count++;
108 return in;
109
110 }
111 ostream& operator<<(ostream& out, BigNum& b) //重载输出运算符
112 {
113 int i;
114 cout << b.a[b.len - 1];
115 for(i = b.len - 2 ; i >= 0 ; i--)
116 {
117 cout.width(DLEN);
118 cout.fill('0');
119 cout << b.a[i];
120 }
121 return out;
122 }
123
124 BigNum BigNum::operator+(const BigNum & T) const //两个大数之间的相加运算
125 {
126 BigNum t(*this);
127 int i,big; //位数
128 big = T.len > len ? T.len : len;
129 for(i = 0 ; i < big ; i++)
130 {
131 t.a[i] +=T.a[i];
132 if(t.a[i] > MAXN)
133 {
134 t.a[i + 1]++;
135 t.a[i] -=MAXN+1;
136 }
137 }
138 if(t.a[big] != 0)
139 t.len = big + 1;
140 else
141 t.len = big;
142 return t;
143 }
144 BigNum BigNum::operator-(const BigNum & T) const //两个大数之间的相减运算
145 {
146 int i,j,big;
147 bool flag;
148 BigNum t1,t2;
149 if(*this>T)
150 {
151 t1=*this;
152 t2=T;
153 flag=0;
154 }
155 else
156 {
157 t1=T;
158 t2=*this;
159 flag=1;
160 }
161 big=t1.len;
162 for(i = 0 ; i < big ; i++)
163 {
164 if(t1.a[i] < t2.a[i])
165 {
166 j = i + 1;
167 while(t1.a[j] == 0)
168 j++;
169 t1.a[j--]--;
170 while(j > i)
171 t1.a[j--] += MAXN;
172 t1.a[i] += MAXN + 1 - t2.a[i];
173 }
174 else
175 t1.a[i] -= t2.a[i];
176 }
177 t1.len = big;
178 while(t1.a[t1.len - 1] == 0 && t1.len > 1)
179 {
180 t1.len--;
181 big--;
182 }
183 if(flag)
184 t1.a[big-1]=0-t1.a[big-1];
185 return t1;
186 }
187
188 BigNum BigNum::operator*(const BigNum & T) const //两个大数之间的相乘运算
189 {
190 BigNum ret;
191 int i,j,up;
192 int temp,temp1;
193 for(i = 0 ; i < len ; i++)
194 {
195 up = 0;
196 for(j = 0 ; j < T.len ; j++)
197 {
198 temp = a[i] * T.a[j] + ret.a[i + j] + up;
199 if(temp > MAXN)
200 {
201 temp1 = temp - temp / (MAXN + 1) * (MAXN + 1);
202 up = temp / (MAXN + 1);
203 ret.a[i + j] = temp1;
204 }
205 else
206 {
207 up = 0;
208 ret.a[i + j] = temp;
209 }
210 }
211 if(up != 0)
212 ret.a[i + j] = up;
213 }
214 ret.len = i + j;
215 while(ret.a[ret.len - 1] == 0 && ret.len > 1)
216 ret.len--;
217 return ret;
218 }
219 BigNum BigNum::operator/(const int & b) const //大数对一个整数进行相除运算
220 {
221 BigNum ret;
222 int i,down = 0;
223 for(i = len - 1 ; i >= 0 ; i--)
224 {
225 ret.a[i] = (a[i] + down * (MAXN + 1)) / b;
226 down = a[i] + down * (MAXN + 1) - ret.a[i] * b;
227 }
228 ret.len = len;
229 while(ret.a[ret.len - 1] == 0 && ret.len > 1)
230 ret.len--;
231 return ret;
232 }
233 long long BigNum::operator %(const long long & b) const //大数对一个int类型的变量进行取模运算
234 {
235 long long i,d=0;
236 for (i = len-1; i>=0; i--)
237 {
238 d = ((d * (MAXN+1))% b + (long long)a[i])% b;
239 }
240 return d;
241 }
242 BigNum BigNum::operator^(const int & n) const //大数的n次方运算
243 {
244 BigNum t,ret(1);
245 int i;
246 if(n<0)
247 exit(-1);
248 if(n==0)
249 return 1;
250 if(n==1)
251 return *this;
252 int m=n;
253 while(m>1)
254 {
255 t=*this;
256 for( i=1;i<<1<=m;i<<=1)
257 {
258 t=t*t;
259 }
260 m-=i;
261 ret=ret*t;
262 if(m==1)
263 ret=ret*(*this);
264 }
265 return ret;
266 }
267 bool BigNum::operator>(const BigNum & T) const //大数和另一个大数的大小比较
268 {
269 int ln;
270 if(len > T.len)
271 return true;
272 else if(len == T.len)
273 {
274 ln = len - 1;
275 while(a[ln] == T.a[ln] && ln >= 0)
276 ln--;
277 if(ln >= 0 && a[ln] > T.a[ln])
278 return true;
279 else
280 return false;
281 }
282 else
283 return false;
284 }
285 bool BigNum::operator >(const int & t) const //大数和一个int类型的变量的大小比较
286 {
287 BigNum b(t);
288 return *this>b;
289 }
290
291 void BigNum::print() //输出大数
292 {
293 int i;
294 cout << a[len - 1];
295 for(i = len - 2 ; i >= 0 ; i--)
296 {
297 cout.width(DLEN);
298 cout.fill('0');
299 cout << a[i];
300 }
301 cout << endl;
302 }
303
304 BigNum Fib[1005];
305 const long long mod=258280327;
306 char str[10000];
307
308 int main(void)
309 {
310 Fib[1]=Fib[2]=BigNum(1);
311 for(int i=3;i<=1000;i++)
312 Fib[i]=Fib[i-2]+Fib[i-1];
313 int T; cin>>T;
314 while(T--)
315 {
316 int n; scanf("%d",&n);
317 scanf("%s",str);
318 BigNum m(str);
319 for(int i=1;i<=1000;i++)
320 {
321 if(Fib[i]>m+BigNum(1))
322 {
323 BigNum ans;
324 ans=(m-Fib[i-2])%mod;
325 ans.print();
326 break;
327 }
328 }
329 }
330 return 0;
331 }