【POJ1745】Divisibility

缺乏、安全感 2022-07-19 02:49 134阅读 0赞

<table style="font-family:Simsun"> 
 <tbody> 
  <tr> 
   <td> 
    <div style="text-align:center; font-size:18pt; font-weight:bold; color:blue">
      Divisibility 
    </div> 
    <div style="text-align:center; font-size:12pt"> 
     <table> 
      <tbody> 
       <tr> 
        <td><strong>Time Limit:</strong>&nbsp;1000MS</td> 
        <td>&nbsp;</td> 
        <td><strong>Memory Limit:</strong>&nbsp;10000K</td> 
       </tr> 
       <tr> 
        <td><strong>Total Submissions:</strong>&nbsp;11568</td> 
        <td>&nbsp;</td> 
        <td><strong>Accepted:</strong>&nbsp;4155</td> 
       </tr> 
      </tbody> 
     </table> 
    </div> <p style="font-size:18pt; font-weight:bold; color:blue">Description</p> 
    <div style="font-family:'Times New Roman',Times,serif; font-size:12pt">
      Consider an arbitrary sequence of integers. One can place + or - operators between integers in the sequence, thus deriving different arithmetical expressions that evaluate to different values. Let us, for example, take the sequence: 17, 5, -21, 15. There are eight possible expressions: 17 + 5 + -21 + 15 = 16&nbsp; 
     <br> 17 + 5 + -21 - 15 = -14&nbsp; 
     <br> 17 + 5 - -21 + 15 = 58&nbsp; 
     <br> 17 + 5 - -21 - 15 = 28&nbsp; 
     <br> 17 - 5 + -21 + 15 = 6&nbsp; 
     <br> 17 - 5 + -21 - 15 = -24&nbsp; 
     <br> 17 - 5 - -21 + 15 = 48&nbsp; 
     <br> 17 - 5 - -21 - 15 = 18&nbsp; 
     <br> We call the sequence of integers divisible by K if + or - operators can be placed between integers in the sequence in such way that resulting value is divisible by K. In the above example, the sequence is divisible by 7 (17+5+-21-15=-14) but is not divisible by 5.&nbsp; 
     <br> 
     <br> You are to write a program that will determine divisibility of sequence of integers.&nbsp; 
     <br> 
    </div> <p style="font-size:18pt; font-weight:bold; color:blue">Input</p> 
    <div style="font-family:'Times New Roman',Times,serif; font-size:12pt">
      The first line of the input file contains two integers, N and K (1 &lt;= N &lt;= 10000, 2 &lt;= K &lt;= 100) separated by a space.&nbsp; 
     <br> The second line contains a sequence of N integers separated by spaces. Each integer is not greater than 10000 by it's absolute value.&nbsp; 
     <br> 
    </div> <p style="font-size:18pt; font-weight:bold; color:blue">Output</p> 
    <div style="font-family:'Times New Roman',Times,serif; font-size:12pt">
      Write to the output file the word "Divisible" if given sequence of integers is divisible by K or "Not divisible" if it's not. 
    </div> <p style="font-size:18pt; font-weight:bold; color:blue">Sample Input</p> <pre style="font-family:'Courier New',Courier,monospace; font-size:12pt">4 7
17 5 -21 15</pre> <p style="font-size:18pt; font-weight:bold; color:blue">Sample Output</p> <pre style="font-family:'Courier New',Courier,monospace; font-size:12pt">Divisible
</pre> <p style="font-size:18pt; font-weight:bold; color:blue">Source</p> 
    <div style="font-family:'Times New Roman',Times,serif; font-size:12pt"> 
     <a href="http://poj.org/searchproblem?field=source&amp;key=Northeastern+Europe+1999" style="text-decoration:none" rel="nofollow">Northeastern Europe 1999</a> 
    </div> </td> 
  </tr> 
 </tbody> 
</table>

好题，用到了同余定理，又融入了动态规划思想

#include<cstdio>
    #include<cstring>
    #include<algorithm>
    using namespace std;
    bool dp[10005][105];
    int a[10005];
    int main() {
    	int n,k;
    	while(scanf("%d%d",&n,&k)!=EOF) {
    		memset(dp,0,sizeof(dp));
    		for(int i=0; i<n; i++) scanf("%d",&a[i]);
    		dp[0][((a[0]%k)+k)%k]=true;
    		for(int i=1; i<n; i++) {
    			for(int j=0; j<k; j++) {
    				if(dp[i-1][j]) {
    					dp[i][((j+a[i])%k+k)%k]=true;
    					dp[i][((j-a[i])%k+k)%k]=true;
    				}
    			}
    		}
    		printf(dp[n-1][0]?"Divisible\n":"Not divisible\n");
    	}
    	return 0;
    }

[题目链接][Link 1]

[Link 1]: http://poj.org/problem?id=1745