2016 Multi-University Training Contest 2(部分) - dblank

# 2016 Multi-University Training Contest 2(部分)

<h2>1001 Acperience</h2>

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<map>
#include<cstring>
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<cmath>
using namespace std;
const double eps = 1e-10;
const int inf = 0x3f3f3f3f, N = 1e6 + 10, Mod = 100000007;
typedef long long ll;
int w[N];
ll gcd(ll a, ll b)
{
return b == 0 ? a : gcd(b, a%b);
}
int main()
{
int t;
cin>>t;
while(t--)
{
ll n;
scanf("%lld", &n);
ll sum = 0, x = 0;
for(int i = 1; i<=n; i++)
{
scanf("%d", &w[i]);
if(w[i]<0)
w[i] = -w[i];
sum += 1LLw[i]w[i];
x += w[i];
}
x*=x;
if(x/n == sum)
printf("0/1n");
else
{
ll G = gcd(x, 1LL*n);
x/=G;
n/=G;
printf("%lld/%lldn", sum*n-x, n);
}
}
return 0;
}

<h2>1005  Eureka</h2>

#include<cstdio>
#include<algorithm>
#include<map>
#include<cstring>
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<cmath>
#include<iostream>
using namespace std;
const double eps = 1e-10;
const int inf = 0x3f3f3f3f, N = 1e3 + 10, Mod = 1000000007;
typedef long long ll;
using namespace std;
struct Point
{
int x, y;
Point() {}
Point(int _x, int _y): x(_x), y(_y) {}
Point operator - (const Point &rhs) const
{
return Point(x - rhs.x, y - rhs.y);
}
bool operator < (const Point &rhs) const
{
return x < rhs.x || (x == rhs.x && y < rhs.y);
}
bool operator == (const Point &rhs) const
{
return x == rhs.x && y == rhs.y;
}
void GCD()
{
int g = std::__gcd(abs(x), abs(y));
if (g) x /= g, y /= g;
}
};
int main()
{
Point p[N], q[N];
int bit[N];
bit[0] = 1;
for(int i = 1; i<=1000; i++)
{
bit[i] = bit[i-1]*2%Mod;
}
int t;
cin>>t;
while(t--)
{
int n;
scanf("%d", &n);
for(int i = 0; i<n; i++)
{
scanf("%d%d", &p[i].x, &p[i].y);
}
sort(p, p+n);
int ans = 0;
for(int i = 0; i<n; i++)
{
int cnt = 0, k = 0;
for(int j = i + 1; j<n; j++)
{
if(p[j] == p[i])
cnt++;
else
q[k++] = p[j] - p[i];
}
for(int j = 0; j<k; j++) q[j].GCD();
ans = (ans + bit[cnt] - 1)%Mod;
sort(q, q+k);
for (int x = 0, y; x < k; x = y)
{
for (y = x; y < k && q[x] == q[y]; ++y);
ans = (ans + 1LLbit[cnt](bit[y-x]-1))%Mod;
}
}
printf("%dn", ans);
}
return 0;
}


<h2>1009 It's All In The Mind</h2>

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<map>
#include<cstring>
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<cmath>
using namespace std;
const double eps = 1e-10;
const int inf = 0x3f3f3f3f, N = 1e5 + 10, Mod = 100000007;
typedef long long ll;
int gcd(int a, int b)
{
return b == 0 ? a : gcd(b, a%b);
}
int a[N], mx[N];
int main()
{
int t;
cin>>t;
while(t--)
{
int n, m;
scanf("%d%d", &n, &m);
memset(a, -1, sizeof(a));
int x, y;
for(int i = 1; i<=m; i++)
{
scanf("%d%d", &x, &y);
a[x] = y;
}
mx[n+1] = 0;
for(int i = n; i>=1;i--)
{
mx[i] = max(mx[i+1],a[i]);
}
int maxx;
for(int i = 1; i<=n; i++)
{
if(i==1)
{
if(a[i] == -1)
a[i] = 100;
maxx = a[i];
}
else
{
if(a[i]==-1 && i>=3)
a[i] = mx[i+1], maxx = min(maxx,a[i]);
else if(a[i] == -1 && i <3)
a[i] = maxx;
else
maxx = min(a[i], maxx);
}
}
int sum = 0;
x=  0;
for(int i = 1; i<=min(2, n); i++)
x+= a[i];
for(int i = 1; i<=n; i++)
sum+=a[i];
int G = gcd(sum, x);
printf("%d/%dn", x/G, sum/G);
}
return 0;
}

<h2>1011 Keep On Movin</h2>

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<map>
#include<cstring>
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<cmath>
using namespace std;
const double eps = 1e-10;
const int inf = 0x3f3f3f3f, N = 1e5 + 10, Mod = 100000007;
typedef long long ll;
int a[N];
int main()
{
int n, t;
cin>>t;
while(t--)
{
scanf("%d", &n);
ll sum  = 0;
for(int i = 1; i<=n; i++)
scanf("%d", &a[i]);
int ans = 0;
for(int i  = 1; i<=n; i++)
{
if(a[i] & 1)
{
sum += (a[i] - 1)/2;
ans ++;
}
else
{
sum += a[i]/2;
}
}
if(ans == 0)
cout<<sum * 2<<endl;
else if(sum % ans == 0)
cout<<sum/ans*2 + 1<<endl;
else
cout<<sum/ans * 2 + 1<<endl;
}
return 0;
}

<h2>1012 La Vie en rose</h2>

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<map>
#include<cstring>
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<cmath>
using namespace std;
const double eps = 1e-10;
const int inf = 0x3f3f3f3f, N = 1e5 + 10, Mod = 100000007;
typedef long long ll;
int Next[N], n, m;
char s[N*10], x[N];
int main()
{
int t;
cin>>t;
while(t--)
{
scanf("%d%d", &n, &m);
scanf("%s", s);
scanf("%s", x);
for(int i = 0;i<n; i++)
{
int ok = 1;
for(int j = 0; j<m; j++)
{
if(x[j] != s[i+j])
{
if(x[j+1] == s[j+i] && x[j] == s[i+j+1])
j++;
else
{
ok = 0;
break;
}
}
}
if(ok) printf("1");
else printf("0");
}
printf("n");
}
return 0;
}