窒息的一场，1007因为mod太多次了被卡常，t了11发；04因为1007心态崩了写不完最后也没a
Scoring Board
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 524288/524288 K (Java/Others)
Problem Description
In programming contests, the scoring board shows each team’s judge results. Assume there is only one problem in the contest, the scoring board will show according to the rules below:
When there is no submissions, the scoring board will show “-”.
When there is no “WA” before “AC”, the scoring board will show “+”.
When the team failed to solve the problem, the scoring board will show “-k”,where k is the number of “WA”.
When the team passed the problem with several tries, the scoring board will show “+k”, where k is the number of “WA” before “AC”.
Please write a program to show the scoring board.
InputThe first line of the input contains an integer T(1 ≤ T ≤ 50), denoting the number of test cases.
In each test case, there is one integer n(0 ≤ n ≤ 50) in the first line, denoting the number of submissions.
In the second line, there are n strings s1, s2, . . . , sn(si ∈ {“AC”, “WA”}), denoting the judge results of each submission. The submissions have already been sorted by time.
OutputFor each test case, print a single line, denoting what the scoring board shows.
Sample Input
5 4 WA WA WA AC 5 WA WA WA AC WA 1 AC 2 WA WA 0
Sample Output
+3 +3 + -2 -
签到
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
const int maxn=(int)2e5+100;
int n;
string s[55];
void solve(){
scanf("%d",&n);
rep(i,1,n) cin>>s[i];
if(n==0) {printf("-\n");return;}
rep(i,1,n) if(s[i]=="AC"){
if(i==1) {printf("+\n");return;}
else if(i>1){
printf("+%d\n",i-1);
return;
}
}
printf("-%d\n",n);
}
int main(){
int T;cin>>T;
while(T--) solve();
}
Catering
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 524288/524288 K (Java/Others)
Problem Description
Mr. Bread owns a catering company and business is booming. The company is planning to open some new restaurants. There are n possible locations to open restaurant, the i-th location will hire ai staff, and will need bi staff when things are busy.
The company wants to choose as many as possible locations to open new restaurants. The only constrait is that every new restaurant should have enough staff in busy. Fortunately, there will be at most one restaurant in busy each day, so a plan is valid if ∑ai ≥ max(bi).
Please write a program to determine how many locations can be choosen.
InputThe first line of the input contains an integer T(1 ≤ T ≤ 10000), denoting the number of test cases.
In each test case, there is one integer n(1 ≤ n ≤ 100000) in the first line, denoting the number of possible locations.
For the next n lines, each line contains two integers ai , bi(1 ≤ ai , bi ≤ 1e9), describing each location.
It is guaranteed that ∑n ≤ 1e6.
OutputFor each test case, print a single line containing an integer, denoting the maximum number of choosen locations.
Sample Input
2 2 3 4 2 5 2 3 4 2 6
Sample Output
2 0
签到
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
const int maxn=(int)1e5+100;
int n;
ll pre[maxn];
struct node{
int a,b;
}p[maxn];
int cmp(node a,node b){
return a.b<b.b;
}
void solve(){
scanf("%d",&n);
rep(i,1,n) scanf("%d%d",&p[i].a,&p[i].b);
sort(p+1,p+1+n,cmp);
rep(i,1,n) pre[i]=pre[i-1]+p[i].a;
dep(i,n,1) if(p[i].b<=pre[i]) {printf("%d\n",i);return;}
printf("0\n");
}
int main(){
int T;cin>>T;
while(T--) solve();
}
Toy Cars
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 524288/524288 K (Java/Others)
Problem Description
Hamster is a little boy - he is only three years old and enjoys playing with toy cars very much. Hamster has n different cars, labeled by 1, 2, . . . , n. They are kept on a long straight trail from left to right. The i-th car occupies the interval [li, ri] of the trail. Two adjacent cars can touch, but can’t overlap, so li ≥ ri−1 always holds for all i= 2, 3, . . . , n.
You are a guest visiting Hamster’s house. Hamster invites you to play toy cars together. He will give you m commands. There are three kinds of commands:
L x k, move the x-th toy car to the left by k. That is, assume the x-th car is at [lx, rx], move it to [lx − k, rx − k]. Negative coordinates are allowed.
R x k, move the x-th toy car to the right by k. That is, assume the x-th car is at [lx, rx], move it to [lx + k, rx + k].
? x, you should tell Hamster lx.
Note that the car being moved might “bump into” another car. The moving car can push other cars if touched.
Please write a program to help Hamster play toy cars.
InputThe first line of the input contains an integer T(1 ≤ T ≤ 10), denoting the number of test cases.
In each test case, there are two integers n, m(1 ≤ n, m ≤ 2000) in the first line, denoting the number of toy cars and commands.
For the next n lines, each line contains two integers li, ri(1 ≤ li ≤ ri ≤ 1e8), describing each toy car. It is guaranteed that li ≥ ri−1 for all i = 2, 3, . . . , n.
For the next m lines, each line describes an event, and it is guaranteed that 1 ≤ x ≤ n and 1 ≤ k ≤ 1e5.
OutputFor each query command, print a single line containing an integer, denoting the answer.
Sample Input
1 4 5 1 2 4 6 6 9 9 10 L 2 2 ? 2 L 2 2 ? 2 ? 1
Sample Output
2 0 -1
暴力模拟即可
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
const int maxn=(int)2e5+100;
int n,m;
struct node{
int l,r;
}p[2019];
void solve(){
scanf("%d%d",&n,&m);
rep(i,1,n) scanf("%d%d",&p[i].l,&p[i].r);
rep(i,1,m){
char op[2];scanf("%s",op);
if(op[0]=='L'){
int x,k;scanf("%d%d",&x,&k);
p[x].r-=k;p[x].l-=k;
int tem=x;
while(tem>1&&p[tem].l<p[tem-1].r){
int len=p[tem-1].r-p[tem-1].l;
p[tem-1].r=p[tem].l;
p[tem-1].l=p[tem-1].r-len;
tem--;
}
}
else if(op[0]=='R'){
int x,k;scanf("%d%d",&x,&k);
p[x].r+=k;p[x].l+=k;
int tem=x;
while(tem<n&&p[tem].r>p[tem+1].l){
int len=p[tem+1].r-p[tem+1].l;
p[tem+1].l=p[tem].r;
p[tem+1].r=p[tem+1].l+len;
tem++;
}
}
else{
int x;scanf("%d",&x);
printf("%d\n",p[x].l);
}
}
}
int main(){
int T;cin>>T;
while(T--) solve();
}
Factorization
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 524288/524288 K (Java/Others)
Problem Description
You are given a positive integer n(n > 1). Consider all the different prime divisors of n. Each of them is included in the expansion n into prime factors in some degree.
Assume n = pe11pe22...pemm , where pi are different prime divisors of n and ei ≥ 1. Your task is to find the greatest common divisor of e1, e2, . . . , em.
InputThe first line of the input contains an integer T(1 ≤ T ≤ 10000), denoting the number of test cases.
In each test case, there is only one integer n(2 ≤ n ≤ 1e18).
OutputFor each test case, print a single line containing an integer, denoting the answer.
Sample Input
3 4 6 36
Sample Output
2 1 2
只要求得pow(n,1/ans)为整数的最大的ans即可，注意pow函数精度的问题
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(ll i=(a);i<=(b);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const int maxn=(int)2e5+100;
const int mod=(int)1e9+7;
ll n;
ll qpow(ll base,ll n){
ll res=1;
while(n){
if(n&1) res*=base;
base*=base;
n>>=1;
}
return res;
}
bool check(int x){
ll y=(ll)pow(1.0*n,1.0/x);
rep(i,max(1ll,y-1),y+1) if(qpow(1ll*i,1ll*x)==n) return 1;
return 0;
}
void solve(){
scanf("%lld",&n);
dep(ans,60,2) if(check(ans)){
printf("%d\n",ans);return;
}
printf("1\n");
}
int main(){
int T;cin>>T;
while(T--) solve();
}
Guess the Number
Time Limit: 6000/3000 MS (Java/Others) Memory Limit: 524288/524288 K (Java/Others)
Problem Description
Professor Elephant has n numbers f1, f2, . . . , fn but he doesn’t want to tell you the numbers directly.
Instead, you should give him some money to buy some useful imformation.
You can buy two types of information:
? x, ask the value of fx, each information will cost you cx dollars.
? a[i] b[i], ask the value of fa[i] − fb[i], each information will cost you w[i] dollars.
You can buy information for many times. Please pay as few as possible dollars to make sure that you can know all the n numbers.
InputThe first line of the input contains an integer T(1 ≤ T ≤ 10), denoting the number of test cases.
In each test case, there are two integers n,m(1 ≤ n ≤ 100000, 0 ≤ m ≤ 200000) in the first line, where m denotes the number of information in the form of ? a[i] b[i].
In the second line, there are n integers c1, c2, . . . , cn(1 ≤ ci ≤ 1e9), denoting the cost of type 1.
For the next m lines, each line contains three integers a[i], b[i], w[i](1 ≤ a[i] < b[i] ≤ n, 1 ≤ w[i] ≤ 1e9), describing each information of type 2.
OutputFor each test case, print a single line containing an integer, denoting the minimum cost.
Sample Input
1 2 1 5 7 1 2 4
Sample Output
9
最小生成树模版题
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
const int maxn=(int)2e5+100;
int n,m,c[maxn],ok[maxn],pre[maxn];
struct node{
int a,b,w;
}d[maxn<<1];
int cmp(node a,node b){return a.w<b.w;}
void init(){rep(i,0,n) ok[i]=0,pre[i]=i;}
int find(int x){return x==pre[x]?x:pre[x]=find(pre[x]);}
void join(int x,int y){
x=find(x);y=find(y);
if(x!=y) pre[x]=y;
}
void solve(){
scanf("%d%d",&n,&m); init();
rep(i,1,n){
scanf("%d",&c[i]);
d[i].a=0;d[i].b=i;d[i].w=c[i];
}
rep(i,1,m) scanf("%d%d%d",&d[i+n].a,&d[i+n].b,&d[i+n].w);
sort(d+1,d+1+n+m,cmp);
ll ans=0;int pos=1,cnt=0;
while(cnt<n){
int x=find(d[pos].a),y=find(d[pos].b);
if(x!=y){
ans+=d[pos].w;cnt++;
join(x,y);
}
pos++;
}
printf("%lld\n",ans);
}
int main(){
int T;cin>>T;
while(T--) solve();
}
Permutation
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 524288/524288 K (Java/Others)
Problem Description
In mathematics, a permutation of n is a set of integers p1, p2, . . . , pn where 1 ≤ pi ≤ n and pi ≠ pj for all pairs of (i, j)(i ≠ j).
It is not hard to figure out that the number of permutations of n is n!. In this task, you are given n integers a1, a2, . . . , an, please figure out how many permutations of nare good.
A permutation is good if and only if pi ≤ ai for all i ∈ [1, n].
InputThe first line of the input contains an integer T(1 ≤ T ≤ 10000), denoting the number of test cases.
In each test case, there is one integer n(1 ≤ n ≤ 100000) in the first line.
In the second line, there are n integers a1, a2, ..., an(1 ≤ ai ≤ n).
It is guaranteed that ∑n ≤ 1e6.
OutputFor each test case, print a single line containing an integer, denoting the number of good permutations.
As the answer can be very large, output it modulo 1e9 + 7.
Sample Input
2 3 3 3 3 3 1 3 3
Sample Output
6 2
简单数学题，公式很容易推出来
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
const int maxn=(int)1e5+100;
const int mod=(int)1e9+7;
int n,a[maxn];
void solve(){
scanf("%d",&n);
rep(i,1,n) scanf("%d",&a[i]);
sort(a+1,a+1+n);
ll ans=1;
rep(i,1,n) ans=(ans*(1ll*a[i]-i+1))%mod;
printf("%lld\n",ans);
}
int main(){
int T;cin>>T;
while(T--) solve();
}
Math Expression
Time Limit: 6000/3000 MS (Java/Others) Memory Limit: 524288/524288 K (Java/Others)
Problem Description
Given a sequence of integers a1, a2, . . . , an. You should insert exactly one operation between ai and ai+1 for all i ∈ [1, n − 1]. The only operations you can choose to insert are “+” and “×”, so there are 2n−1 ways in total.
Your task is to count how many possible ways of insertion that the value of the final math expression is a multiple of integer k.
For example, assume the sequence is 2, 1, 2 and k = 2, there are 4 possible ways of insertion:
2 + 1 + 2 = 5, is not a multiple of 2.
2 + 1 × 2 = 4, is a multiple of 2.
2 × 1 + 2 = 4, is a multiple of 2.
2 × 1 × 2 = 4, is a multiple of 2.
InputThe first line of the input contains an integer T(1 ≤ T ≤ 10), denoting the number of test cases.
In each test case, there are two integers n,k(2 ≤ n, k ≤ 300) in the first line.
In the second line, there are n integers a1, a2, . . . , an(1 ≤ ai ≤ 1e9), denoting the sequence.
OutputFor each test case, print a single line containing an integer, denoting the number of possible ways of insertion. As the answer can be very large, output it modulo 1e9 + 7.
Sample Input
1 3 2 2 1 2
Sample Output
3
dp[i][j]维护前i个数中%k=j的方案数，然后枚举上一个‘+’出现的位置
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
const int maxn=(int)2e5+100;
const int mod=(int)1e9+7;
int n,k,a[310];
int dp[310][310];//前i个数中%k=j的方案数
void init(){
rep(i,0,n) rep(j,0,k-1){
if(i==0&&j==0) dp[i][j]=1;
else dp[i][j]=0;
}
}
void solve(){
scanf("%d%d",&n,&k);
rep(i,1,n) {scanf("%d",&a[i]);a[i]%=k;} init();
rep(i,1,n){
int now=1;
dep(j,i,1){ //枚举上一个‘+’的位置
now=now*a[j]%k;
rep(c,0,k-1){
dp[i][(c+now)%k]+=dp[j-1][c];
dp[i][(c+now)%k]%=mod;
}
}
}
printf("%d\n",dp[n][0]);
}
int main(){
int T;cin>>T;
while(T--) solve();
}
Map Tiles
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 524288/524288 K (Java/Others)
Problem Description
You are a developer of a 2D computer game. Your job is to draw maps in the game. The designer has already designed the map of the game, so what you need to do is to cut the picture into very small square tiles.
Assume the size of the picture is w × h, the picture can be saved as a matrix g[0 . . . w − 1, 0 . . . h − 1].
You need to find the smallest integer k that g[i, j] = g[i mod k, j mod k] always holds for all pairs of (i, j)(0 ≤ i < w, 0 ≤ j < h).
InputThe first line of the input contains an integer T(1 ≤ T ≤ 10), denoting the number of test cases.
In each test case, there are two integers w, h(1 ≤ w,h ≤ 200) in the first line.
For the next w lines, each line contains a string of length h, which only contains lower-case letters, denoting the picture.
OutputFor each test case, print a single line containing an integer, denoting the smallest value of k.
Sample Input
3 3 6 ababab cdcdcd ababab 2 2 ab cd 3 3 aaa aaa aaa
Sample Output
2 2 1
暴力
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
const int maxn=(int)2e5+100;
int n,m;
char mp[220][220];
void solve(){
scanf("%d%d",&n,&m);
rep(i,0,n-1) scanf("%s",mp[i]);
rep(k,1,max(n,m)){
int ok=1;
rep(i,0,n-1) rep(j,0,m-1) if(mp[i][j]!=mp[i%k][j%k]){ok=0;break;}
if(ok) {printf("%d\n",k);return;}
}
}
int main(){
int T;cin>>T;
while(T--) solve();
}
